Maximum Subarray Sum

Given an array of integers, find the maximum sum of any contiguous subarray. In other words, for an array \(A\) of length \(n\), determine the maximum possible value of the sum:

\(\sum_{k=i}^{j} A[k]\) where \(0 \leq i \leq j < n\).

This problem can be solved efficiently with Kadane's algorithm in \(O(n)\) time.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer (n) denoting the number of elements in the array. The second line contains (n) space-separated integers representing the array's elements.

outputFormat

Output to standard output (stdout) a single integer which is the maximum sum of any contiguous subarray.## sample

5
1 2 3 -2 5

9