Maximum Subarray Sum

Given an array of integers, your task is to find the maximum sum of a contiguous subarray. In other words, you need to compute the maximum value of the sum

\( S = \sum_{i=l}^{r} a_i \)

over all intervals \( [l, r] \) such that \( 1 \leq l \leq r \leq n \). If all numbers are negative, the answer is defined to be 0.

inputFormat

The input is given via stdin in the following format:

• The first line contains a single integer \( n \), 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 to stdout: the maximum sum of a contiguous subarray, or 0 if all numbers are negative.

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

6