Maximum Subarray (Kadane's Algorithm)

Find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Use Kadane's Algorithm: Track current sum and max sum. If current sum becomes negative, reset it. Example: [-2,1,-3,4,-1,2,1,-5,4] → Subarray [4,-1,2,1] has largest sum = 6

Input

Line 1: n. Line 2: n space-separated integers.

Output

The maximum subarray sum.

Sample

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

Expected

6