6. Maximum Subarray Sum

Difficulty: medium · Array, Dynamic Programming

Problem

Given an integer array `nums`, find the **contiguous, non-empty** subarray with the largest sum and print that sum.

Input

The first line holds `n`. The second holds `n` integers.

Output

Print the largest subarray sum.

Example 1

Input:
9
-2 1 -3 4 -1 2 1 -5 4
Output:
6

Explanation: The subarray [4 -1 2 1] (indices 3 to 6) has the largest sum, 6.

Example 2

Input:
1
1
Output:
1

Explanation: The subarray [1] (indices 0 to 0) has the largest sum, 1.

Example 3

Input:
5
5 4 -1 7 8
Output:
23

Explanation: The subarray [5 4 -1 7 8] (indices 0 to 4) has the largest sum, 23.

Example 4

Input:
3
-3 -2 -5
Output:
-2

Explanation: The subarray [-2] (indices 1 to 1) has the largest sum, -2.

Example 5

Input:
4
1 2 3 4
Output:
10

Explanation: The subarray [1 2 3 4] (indices 0 to 3) has the largest sum, 10.

Example 6

Input:
6
2 -8 3 -2 4 -10
Output:
5

Explanation: The subarray [3 -2 4] (indices 2 to 4) has the largest sum, 5.

Example 7

Input:
5
-1 0 -2 0 -3
Output:
0

Explanation: The subarray [0] (indices 1 to 1) has the largest sum, 0.

Example 8

Input:
7
-5 6 -1 -1 6 -20 3
Output:
10

Explanation: The subarray [6 -1 -1 6] (indices 1 to 4) has the largest sum, 10.

Example 9

Input:
10
8 7 -8 7 -3 5 8 3 -8 -1
Output:
27

Explanation: The subarray [8 7 -8 7 -3 5 8 3] (indices 0 to 7) has the largest sum, 27.

Example 10

Input:
9
-6 -4 3 -1 2 -3 -8 -2 -6
Output:
4

Explanation: The subarray [3 -1 2] (indices 2 to 4) has the largest sum, 4.

Constraints

- 1 <= n <= 10^5 - -10^4 <= nums[i] <= 10^4

Solutions are judged against 10 sample and 5 hidden tests. Sign in to solve it · All problems