Maximum Subarray Sum

Given an array of N integers, find the contiguous non-empty subarray that has the largest sum and output that sum. ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​‌​​​​‌‌​​​​​​‌‌‌​​‌​​‌‌​‌‌​​​‌‌​‌​‌​‌‌​​‌‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌‌​​‌​​‌‌​​​​

Input Format

• Line 1: An integer N (1 ≤ N ≤ 200,000), the number of elements in the array.
• Line 2: N space-separated integers A[0], A[1], ..., A[N-1] (-10^9 ≤ A[i] ≤ 10^9).

---

Output Format

• Print a single integer — the maximum contiguous subarray sum. ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​‌​​​​‌‌​​​​​​‌‌‌​​‌​​‌‌​‌‌​​​‌‌​‌​‌​‌‌​​‌‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌‌​​‌​​‌‌​​​​

---

Example 1

Input:

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

Output:

6

Explanation: The contiguous subarray [4, -1, 2, 1] has the largest sum: 4 + (-1) + 2 + 1 = 6.

---

Example 2

Input:

5
5 4 -1 7 8

Output: ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​‌​​​​‌‌​​​​​​‌‌‌​​‌​​‌‌​‌‌​​​‌‌​‌​‌​‌‌​​‌‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌‌​​‌​​‌‌​​​​```text 23

**Explanation:**
The entire array `[5, 4, -1, 7, 8]` has the sum: `5 + 4 + (-1) + 7 + 8 = 23`.
​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​‌​​​​‌‌​​​​​​‌‌‌​​‌​​‌‌​‌‌​​​‌‌​‌​‌​‌‌​​‌‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌‌​​‌​​‌‌​​​​

5
5 4 -1 7 8

23

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

6