Maximum Contiguous Subarray Sum

Given an integer array, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. This is a classic problem that can be solved efficiently using Kadane's algorithm. In mathematical terms, if the array is (a_1, a_2, \dots, a_n), you need to compute (\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k).

inputFormat

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

outputFormat

Output the maximum sum of a contiguous subarray. The output should be written to standard output (stdout).## sample

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

6