Maximum Subarray

Question (LC.53)

Find the contiguous subarray with the maximum sum.

Example

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Return: [4, -1, 2, 1] = 6

Analysis

We want to find a subarray with the maximum sum. For the brute force solution , we obviously need to keep a global max and a current sum. Then for each number in the array, we search for the contiguous subarray. The time complexity is O(n^2).

Code

public int maxSubArray(int[] nums) {
    int maxSum = Integer.MIN_VALUE;
    if (nums == null || nums.length == 0)
        return maxSum;
    int currentSum = 0;

    for (int i = 0; i < nums.length; i++) {
        // search the largest contiguous subarray
        for (int j = i; j < nums.length; j++) {
            currentSum += nums[j];
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
        currentSum = 0;
    }

    return maxSum;
}

Complexity

O(n^2) time and O(1) space

Follow Up

Can you do it in linear time?

Analysis

We can use some space to trade off some time. This is an optimization problem. So we want to give DP a try to see if we can spot some overlapping problems. Intuitively, the subproblem's format should look like maxSubarray(int A[], int start, int end) and the original problem maxSubarray(int A[], int 0, int A.length-1). However, this format is hard to think of how the subproblems overlap with each other.

One of the problems with the first format is that it formalizes the subproblems in substrings which are O(n^2) in size. We want to solve by prefix for this problem (removing from the end O(n) size). Defining the subproblems as maxSubarray(int A[], int end) will be a better approach. Then we can write out the recurrence maxSubarray(A[], n) = A[n] + Math.max(maxSubarray(A[], n-1), 0). The topological order is for i from 0 to n-1. The original problem is maxSubarray(A[], A.length-1).

for (int i = 0; i < nums.length; i++)
    maxSubarray(A[], n) = A[n] + Math.max(maxSubarray(A[], n-1), 0)

Memoization (Top-down)

int maxSum = Integer.MIN_VALUE;

public int maxSubArray(int[] nums) {
    int[] memo = new int[nums.length];
    dpHelper(nums, memo, nums.length - 1); // the helper helps in filling out the dp table
    return maxSum;
}

private int dpHelper(int[] A, int[] memo, int end) {
    if (end == 0) {
        memo[end] = A[end];
        maxSum = Math.max(maxSum, memo[end]);
        return memo[end];
    } else {
        memo[end] = A[end] + Math.max(dpHelper(A, memo, end-1), 0);
        maxSum = Math.max(maxSum, memo[end]);
        return memo[end];
    }
}

Tabulation (Bottom-up)

public int maxSubArray(int[] nums) {
    int maxSum = nums[0];
    int[] memo = new int[nums.length];
    // initialization
    memo[0] = nums[0];
    // topo order
    for (int i = 1; i < nums.length; i++) {
        // recurrence of dp
        memo[i] = nums[i] + Math.max(memo[i-1], 0);
        maxSum = Math.max(maxSum, memo[i]);
    }
    // solve the original problem
    return maxSum;
}

Sometimes it is easier to create memo[A.length+1]. (not in this simple case)

public int maxSubArray(int[] nums) {
    int maxSum = Integer.MIN_VALUE;
    int[] memo = new int[nums.length + 1];
    // initialization
    memo[0] = maxSum;
    // topo order
    for (int i = 0; i < nums.length; i++) {
        // recurrence of dp
        memo[i+1] = nums[i] + Math.max(memo[i], 0);
        maxSum = Math.max(maxSum, memo[i+1]);
    }
    return maxSum;
}

Complexity

Time = #subproblems x time/subproblem = n * O(1) = O(n) Space = O(n)

Follow Up #2

Can you do in linear time with constant space?

Analysis

Wutttt? DP in constant space?

Follow Up #3 (LC.43)