Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

DP

state: dp[i]指以当前数结尾的subarray的最大值
function: dp[i] =

  1. dp[i - 1] + nums[i] (dp[i - 1] > 0)
  2. nums[i] (dp[i - 1] <= 0)

init: dp[0] = nums[0]
answer: max(dp[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0)
        return 0;
    int[] dp = new int[2];
    dp[0] = nums[0];
    int ans = nums[0];
    
    for (int i = 1; i < nums.length; i++) {
        if (dp[(i - 1) % 2] > 0) {
            dp[i % 2] = dp[(i - 1) % 2] + nums[i];
        } else {
            dp[i % 2] = nums[i];
        }
        ans = Math.max(ans, dp[i % 2]);
    }
    return ans;
}

prefix sum array

subarray的问题大部分都可以用prefix sum array来解
求得prefix sum array, 题目就转变成了 121. Best Time to Buy and Sell Stock. 就是找后面的数和前面的数的差的最大值。
按题目中的示例来说，prefix sum array就是 [-2, -1, -4, 0, -1, 1, 2, -3, 1]. 最大值是prefix[6] - prefix[2] = 6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0)
        return 0;
    int[] prefix = new int[nums.length];
    prefix[0] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        prefix[i] = prefix[i - 1] + nums[i];
    }
    int min = 0;
    int ans = prefix[0];
    for (int i = 0; i < nums.length; i++) {
        ans = Math.max(ans, prefix[i] - min);
        min = Math.min(min, prefix[i]);
    }
    return ans;
}

Kadane’s algorithm

Ref: https://en.wikipedia.org/wiki/Maximum_subarray_problem

1
2
3
4
5
6
7
8
9
10
11
12
public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0)
        return Integer.MIN_VALUE;
    int maxEndingHere = nums[0];
    int maxSoFar = nums[0];
    for (int i = 1; i < nums.length; i++) {
        maxEndingHere = Math.max(maxEndingHere + nums[i], nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
}