Maximum Subarray Sum (Kadane's)

Maximum Subarray Sum (Kadane's)

Find the maximum possible sum of a contiguous subarray within a given array.

Input format

The first line contains N. The second line contains N space-separated integers.

Output format

Print the maximum possible sum of a non-empty contiguous subarray.

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

1
-1

-1