Maximum Subarray Sum

Given an array of integers, find the contiguous subarray (containing at least one element) which has the largest sum and output its sum.

If the array is empty, output 0.

You can use Kadane's algorithm to solve this problem. The recurrence relation used in Kadane's algorithm is given by: $$current\_sum = \max(a_i, current\_sum + a_i)$$ and the answer is the maximum value of \(current\_sum\) over all indices.

inputFormat

The input is provided via standard input (stdin). The first line contains a single integer (n), representing the number of elements in the array. The second line contains (n) space-separated integers. Note that if (n = 0), the second line will be empty.

outputFormat

Output via standard output (stdout) a single integer representing the sum of the contiguous subarray with the maximum sum.## sample

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

6