Maximum Subarray Sum

Maximum Subarray Sum

Find the largest sum of any contiguous block (Kadane's algorithm).

Input format

The first line has one integer N. The second line has N space-separated integers.

Output format

Print the largest sum of any non-empty contiguous block of the array (Kadane's algorithm).

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

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

6

4
1 2 3 4

10