Finding Maximum Subarray Sum

Given a list of integers containing both positive and negative numbers, your task is to find the sum of the largest contiguous subarray. This problem can be efficiently solved using Kadane's Algorithm which has a linear time complexity of O(n). The core idea of Kadane's algorithm is based on the recurrence:

$$max\_current = \max(num, max\_current + num)$$

At each step, the algorithm updates the maximum sum ending at the current element and, in the process, keeps track of the overall maximum subarray sum.

The input is provided via stdin and the output is expected on stdout.

inputFormat

The first line of the input contains a single integer n (1 ≤ n ≤ 10⁵), representing the number of elements in the array. The second line contains n space-separated integers, each with an absolute value not exceeding 10⁹.

outputFormat

Output a single integer on stdout — the sum of the largest contiguous subarray.

## sample

6
1 -2 3 5 -3 2

8

</p>