Maximum Subarray Sum

Given an array of integers, your task is to find the maximum sum of any contiguous subarray. In other words, if the array is (a_1, a_2, \dots, a_n), you need to compute: [ \text{max u{}} = \max_{1 \leq i \leq j \leq n} \left(\sum_{k=i}^j a_k\right) ] This problem can be efficiently solved using Kadane's algorithm in (O(n)) time.

inputFormat

The input is provided via standard input (stdin). The first line contains an integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers.

outputFormat

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

5
1 -2 3 -1 2

4