Maximum Subarray

• https://leetcode.com/problems/maximum-subarray/

The key is to find sub-optimal structure.

When we scan to A[i], the value if is either A[i] itself, or sum[i-1], where sum[i-1] is the maximum value up to index i-1.

/*
 * Time complexity O(N), space complexity O(N).
 */
public int maxSubArray(int[] nums) {
    int[] sum = new int[nums.length];
    sum[0] = nums[0];
    int max = nums[0];

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

    return max;
}

For the auxiliary array sum with O(n) space complexity, we can reduce it down to O(1), since we only need sum[i-1] each time.

/*
 * Time complexity O(N), space complexity O(1).
 */
public int maxSubArray(int[] nums) {
    int prevSum = nums[0];
    int max = nums[0];

    for (int i = 1; i < nums.length; i++) {
        prevSum = Math.max(prevSum + nums[i], nums[i]);

        max = Math.max(max, prevSum);
    }

    return max;
}