53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing
at least one number) which has the largest sum and return its sum.
  1. DP brutal
public int maxSubArrayBrutal(int[] nums) {
    int result = Integer.MIN_VALUE;
    for(int i = 0; i < nums.length; i++) {
        int sum = 0;
        for(int j = i; j < nums.length; j++) {
            sum += nums[j];
            result = Math.max(sum, result);
        }
    }
    return result;
}
  1. One Pass

Key: Is i the index to start a new sum?


public int maxSubArray(int[] nums) {
    int result = nums[0], sum = result;
    for(int i = 1; i < nums.length; i++) {
        sum += nums[i];
        if(sum < nums[i]) {
            sum = nums[i];
        }
        result = Math.max(result, sum);
    }
    return result;
}

public int maxSubArray(int[] nums) {
    int result = Integer.MIN_VALUE, sum = 0;
    for(int n : nums) {
        sum = sum + n < 0 ? 0 : sum + n; // reset sum when it becoming negative
        result = n < 0 ? Math.max(result, n) : Math.max(result, sum); // imaging an array with only negative elements
    }
    return result;
}