Leetcode: 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.

click to show more practice.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Understand the problem:
The problem asks for finding a subarray which yields in the largest sum. It is not hard to find that for a brute force solution, we try all possible combinations and add them up, so we have totally Cn1 + Cn2 + ... + Cnn = n! combinations. That motivate us find a practical solution in polynomial time.

Note that this problem is ambiguous. In real code interview, you may be asked for two cases. The first case, for a array with only negative numbers, return 0, meaning empty subarray.
The second case is to return the maximal negative value. Both of the cases can pass the OJ here, but the code will look different. 


In this problem, we onlNote that this problem is ambiguous. In real code interview, you may be asked for two cases. The first case, for a array with only negative numbers, return 0, meaning empty subarray.
The second case is to return the maximal negative value. Both of the cases can pass the OJ here, but the code will look different. y consider the second case, where return the maximal negative value. I think that makes more sense to me. Of course, changing to the first case requires little changes in the code. 

DP Solution:
We use an array, s[ ] to store the max(A[i] + s[i - 1], A[i]). That is, the maximum sum of the previous number, or A[i], whoever greater. The purpose is if the previous sum deduct the current number A[i], we discard the previous sum and start the sum from A[i]. 

Code (Java):

public class Solution {
    public int maxSubArray(int[] A) {
        if (A == null || A.length == 0) return 0;
        
        int[] s = new int[A.length];
        s[0] = A[0];
        
        int max = A[0];
        
        for (int i = 1; i < A.length; i++) {
            s[i] = Math.max(s[i - 1] + A[i], A[i]);
            max = Math.max(s[i], max);
        }
        return max;
    }
}

Discussion:
The time complexity is O(n) since we only traverse the array once. The space complexity is O(n) as well. 

An O(1) Space Solution:
Consider the Line 11 in the above solution. s[i] is determined by the maximal s[i - 1] + A[i] and A[i]. So what caused s[i - 1] + A[i] < A[i]. That is obvious, s[i - 1] < 0. So we can devise a constant space solution that when sum < 0, we discarded the previous sum and start from this number. Since we don't need to maintain an array but just a variable sum, its space complexity is O(1).

Code (Java):

public class Solution {
    public int maxSubArray(int[] A) {
        if (A == null || A.length == 0) return 0;
        
        int max = Integer.MIN_VALUE;
        int sum = 0;
        
        for (int i = 0; i < A.length; i++) {
            if (sum < 0) {
                sum = A[i];
            } else {
                sum += A[i];
            }
            max = Math.max(max, sum);
        }
        return max;
    }
}

Divide-and-Conquer Solution:
The idea of divide-and-conquer is similar to the binary search. We first cut the array into three parts, A[0, mid - 1], A[mid], A[mid + 1, len - 1]. As a result, the maximum subarray must exist either in left or right part, or cross the middle point. 

Code (Java):

public class Solution {
    int max = Integer.MIN_VALUE;
    public int maxSubArray(int[] A) {
        if (A == null || A.length == 0) return 0;
        
        return maxSubArray(A, 0, A.length - 1);
    }
    
    private int maxSubArray(int[] A, int lo, int hi) {
        if (lo > hi) return Integer.MIN_VALUE;
        
        int mid = (lo + hi)/2;
        
        int lMax = maxSubArray(A, lo, mid - 1);
        int rMax = maxSubArray(A, mid + 1, hi);
        
        max = Math.max(max, lMax);
        max = Math.max(max, rMax);
        
        // find max from middle to left
        int mlMax = 0;
        int sum = 0;
        for (int i = mid - 1; i >= lo; i--) {
            sum += A[i];
            mlMax = Math.max(mlMax, sum);
        }
        
        // find max from middle to right
        int mrMax = 0;
        sum = 0;
        for (int i = mid + 1; i <= hi; i++) {
            sum += A[i];
            mrMax = Math.max(mrMax, sum);
        }
        
        return Math.max(max, mrMax + mlMax + A[mid]);
        
    }
}

Discussion:
Note in Line 21 and 29, mlMax and mrMax = 0. This 0 is very important and should not be Integer.MIN_VALUE. That is  because in the case where the maximum subarray across the mid point, it could be actually four cases: left + mid, mid, right + mid,  left + mid + right. However, if either left or right sum is less than zero, we can simply discard that part. That is why the mlMax and mrMax start from zero, and we simply calculate the left + mid + right which guarantee covering all cases above. 

For the divide and conquer, the time complexity is O(n logn). That is because for the recursion the time is O(logn), while for each recursion we have two for loops, which could be at worst O(n), so the total time complexity is O(nlogn).

Summary:
Finding the maximum subarray is a classical problem. Make sure you understand the DP solution with O(n) time. 


Update on 4/7/2019:

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int curSum = 0;
        int minPreSum = 0;
        int maxSum = Integer.MIN_VALUE;
        
        for (int i = 0; i < nums.length; i++) {
            curSum += nums[i];
            maxSum = Math.max(maxSum, curSum - minPreSum);
            
            minPreSum = Math.min(minPreSum, curSum);
        }
        
        return maxSum;
        
    }
}