Problem Description

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.

Example 2

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Solution

The problem has two degrees of freedom, one being start index of the subarray and the other being end of the subarray. Brute-force method takes O(N^2) time (two loops). To have better performance, typical ideas include optimizing one loop by better algorithm, e.g. binary search to have O(NlogN). If we want to have O(N) time, we either come up with a clever algorithm adapted to the specific problem (kind of harder), or use DP.

To use DP and have O(N), apparently there is one loop, thus one degree of freedom. We need a one-dimensional dp[i] array. The key is what would dp[i] mean. For example, in this problem, we need to find the max sum of a subarray in an array, we could interprete dp[i] as the max sum of a subarray in the array nums[:i], thus dp[nums.length-1] is the answer of the original problem. However, sometimes, it is hard to build the recursion relation this way. Another common way is to interprete dp[i] as the max sum of a subarray that ends at the index i, and we can take the max value among the dp array to be the anwer of the problem. For this problem, it is easier to use the latter interpretation. If dp[i] is the max value of a subarray ending at i, how should we build dp[i+1] from dp[i]? There are only two options, either dp[i]+nums[i+1] or nums[i+1]. We take the larger value. Thus, we obtain the algorithm. Another optimization is to note that the recusion relation only relies on dp[i] not preivous elements, therefore there is no need to really hold the whole dp array, a constant space complexity would do the work.

Another way to deal with this problem is this: if we want to compute the max sum of a subarray nums[i,j] ending at j, we could use the relation sum[i,j]=sum[:i]-sum[:j]. In other words, we need to find the min sum sum[:j]. Therefore, we record the min sum sum[:j] and use this to compute max sum sum[i,j] at each iteration.

Code

DP

class Solution {
    public int maxSubArray(int[] nums) {
        int currsum = nums[0];
        int res = nums[0];

        for(int end=1; end<nums.length; end++) {
            // currsum: the best subarray ending in i, inclusive
            currsum = Math.max( nums[end], currsum+nums[end] );
            res = Math.max( res, currsum );
        }
        return res;
    }
}

Min Sum and Max Sum

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int min = 0;
        int res = Integer.MIN_VALUE;

        for(int i=0; i<nums.length; i++) {
            sum += nums[i];
            res = Math.max(res, sum-min);
            min = Math.min( min, sum );
        }

        return res;

    }
}