Maximum Subarray Sum

Given an array of integers, find the contiguous subarray (containing at least one number) which has the largest sum. Formally, for an array \(a_1, a_2, \ldots, a_n\), you are to compute:

[ \max_{1 \leq i \leq j \leq n} \left(\sum_{k=i}^{j}a_k\right) ]

This problem is a classic application of Kadane's algorithm that runs in linear time.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

• The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single integer -- the greatest sum of any non-empty contiguous subarray. The result should be printed to standard output (stdout).

9
-2 1 -3 4 -1 2 1 -5 4

6