Maximum Subarray Sum (Kadane's Algorithm)

Given an array of integers, your task is to find the contiguous subarray which has the largest sum and output that sum. This problem can be efficiently solved using Kadane's algorithm. In mathematical terms, if we denote the subarray sum ending at index (i) as (f(i)), then: [ f(i) = \max(a_i, f(i-1) + a_i) \quad \text{for} ; i \geq 1, \quad f(0) = a_0 ] and the answer is (\max_{0 \le i < n} f(i)).

Note: The array will contain at least one element.

inputFormat

The input is read from stdin and consists of two lines. The first line contains an integer (N) representing the number of elements in the array. The second line contains (N) space-separated integers representing the elements of the array.

outputFormat

Output a single integer to stdout which is the sum of the contiguous subarray with the largest sum.## sample

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

6