53. Maximum Subarray

LeetCode

Greedy

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSoFar = nums[0];
        int maxEndingHere = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }
}

Dynamic Programming

Apparently, this is a classic optimization problem, so we can use dynamic programming to solve it.

First, we should define the original problem and the sub-problem, then figure out the connection between them. To find them, we can focus on the transition of the last step.

Because array is consecutive, if an array subarray(i) ends at nums[i] is a maximum subarray, the second largest maximum subarray subarray(i - 1) must ends at nums[i - 1] when it can make subarray(i) larger.

In addition, we may have many maximum subarray, but what we want is the subarray which has the largest sum.

class Solution {
    // dp[i]: the maximum sum of a subarray which ends at nums[i]
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int maxSum = dp[0];
        for (int i = 1; i < nums.length; i++) {
            if (dp[i - 1] > 0) {
                dp[i] = nums[i] + dp[i - 1];
            } else {
                dp[i] = nums[i];
            }
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }
}