53. Maximum Subarray

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.

keep two record, max value so far, and current sum. for each number, add to sum, if sum > max, then set the max-so-far as sum, if sum <0, discard all numbers visited, cause it is not used for the following numbers. but the max-so-far is kept.

Related issue: 152 Maximum Product Subarray

classic dp solution

public class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for(int i=1; i< nums.length;i++){
            if(dp[i-1] <=0 && nums[i] >=0){
              dp[i] = nums[i];
              continue;
            }
            int tmp = dp[i-1] + nums[i];
            if(tmp >= 0) dp[i] = tmp;
            else dp[i] = nums[i];


        }
        int max = dp[0];
        for(int v: dp){
            if(v > max) max = v;
        }
        return max;
    }
}

to improve above solution, notice that only dp[i-1] and dp[i] is used,.

notice when i ==0, is handles specically.

public class Solution {
    public int maxSubArray(int[] nums) {
        int sum =0, max = 0;
        for(int i=0; i< nums.length; i++){
            sum += nums[i];
            if(sum > max || i == 0) max = sum;
            if(sum < 0) sum =0; // if the sum goes below zero, reset the sum to zero as it start counting from next item.
        }

        return max;
    }
}