Maximum Sum of Contiguous Chapters

You are given a sequence of N chapters, where each chapter has a certain number of pages, which can be positive, zero, or negative. Your task is to find a contiguous segment of chapters such that the sum of their pages is maximized.

Formally, given an array of integers \(a_1, a_2, \dots, a_N\), find the maximum value of \(\sum_{i=l}^{r} a_i\) over all choices of indices \(1 \leq l \leq r \leq N\).

This problem is a classic example of the Kadane's Algorithm which solves it in \(O(N)\) time. Use this algorithm or any other efficient method to compute the result.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

• The first line contains a single integer \(N\) representing the number of chapters.
• The second line contains \(N\) space-separated integers representing the number of pages in each chapter.

outputFormat

Output a single integer to standard output (stdout) which is the maximum sum of pages in any contiguous segment of chapters.

5
3 -2 5 -1 4

9