Maximum Subarray Sum

You are given an array of n integers. Your task is to compute the maximum sum of any continuous subarray (i.e., a subarray where the elements are contiguous in the original array). In other words, find the subsequence with consecutive elements that has the largest sum.

If the array contains only negative numbers, then the result should be 0 (this corresponds to taking an empty subarray).

The solution must implement the efficient algorithm (commonly known as Kadane's algorithm).

Mathematically, for an array \(a_1, a_2, \ldots, a_n\), find the value:

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

with the condition that if \(\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k < 0\), then output 0.

inputFormat

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

1. The first line contains a single integer n representing the number of elements in the array.
2. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output a single integer on a new line — the maximum sum of any continuous subarray. If the maximum sum is negative, output 0.

## sample

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

6

</p>