Maximum Subarray Sum

This problem is about finding the maximum sum of a contiguous subarray from a given array of integers. Formally, for an array \( a_1, a_2, \ldots, a_n \), you are to compute:

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

If the array is empty or if every element is negative, the result should be 0 (since taking no element yields sum zero). This problem can be efficiently solved using Kadane's algorithm.

Example:

Input: 9
       -2 1 -3 4 -1 2 1 -5 4
Output: 6

inputFormat

The first line of input contains an integer n (\(0 \leq n \leq 10^5\)), representing the number of elements in the array. The second line contains n space-separated integers, each representing an element of the array.

outputFormat

Output a single integer which is the maximum sum of any contiguous subarray. If the array is empty or if all elements are negative, output 0.

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

6