53. Maximum Subarray

Published on November 19, 2023

Question

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Algorithm

The code1 is wrong solution. Code2 is a valid answer. Code1 is mislead by a two pointer solution and tried to solve that way.

This question can be solve in a dynamic programming way.

For DP, you need to define what is the dp for. Here our dp[i] is until index i, the max sub array for current nums[0, i] array.

Then the equation, how we get the next answer from previous results. I take the example and walk through it, the find the pattern: for the dp[I],

it could be dp[i-1] when current nums[i] is negative which will let the sum become smaller;

or it can be previous max sub array sum plus nums[i], where nums[i] is a positive number and can contribute to a bigger sum so as too a bigger max sub array sum;

Or it can be the number nums[i] itself if it's the first element or previous array part will "compromise" the number, which mean the number itself can be a sub array and big sum.

Or in another view of point, we have two parts. First part is we just went though and got some results, the other part part2 is current number , the nums[I], the answer has three conditions, part1 refers previous condition1, part2 refers to the condition3 and part1 + part2 is the condition2.

In the given example, you can have a dry run and find the 3 pattern.

Code1

class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        if (nums == null || nums.length() == 0) {
            return max;
        }
        
        int sum = nums[0];
        int l = 1, r = 1;
        
        while (r < nums.length()) {
            if (r + 1 < nums.length && nums[r + 1] + sum >= sum) {
                max = Math.max(nums[++r] + sum, max);
            } else {
                if (l < r) {
                    l++;
                    sum -= nums[l];
                } else {
                    r++;
                    sum += nums[r];
                }
                max = Math.max(sum, max);
            }
        }
        return Math.max(sum, max);
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int[] sums = preSums(nums);
        int max = Integer.MIN_VALUE;
        if (nums == null || nums.length() == 0) {
            return max;
        }
        int l = 0,  r = 0;
        while (r < nums.length()) {
            max = Math.max(Math.max(nums[r], sums[r] - sums[l - 1] + nums[r]), max);
            if (max == nums[r]) {
                l = r;
                r++;
            } else if (max == sums[r] - sums[l - 1] + nums[r]) {
                r++;
            } else {
                r++;
            }
        }
        
        return Math.max(sum, max);
        
    }
    
    private int[] preSums(int[] nums) {
        int[] sums = new int[nums.length()];
        for (int i = 0; i < nums.length; i++) {
            if (i == 0) {
                sums[i] = nums[i];
            } else {
                sums[i] = sums[i - 1] + nums[i];
            }
        }
        return sums;
    }
}

Code2

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