LeetCode Maximum Subarray: 4 methods, DP, Divide and Conquer

Overview

I summarize different solutions to the LeetCode problem Maximum Subarray including DP, Divide and Conquer, there are 4 different approaches as far as I know.

Problem Definition

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.

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.

Solutions and Analysis

(1) Brute Force: for every possible contiguous subarray A[i…j] we get the sum and return the maximum one among them. Since we can obtain the sum in constant time (why?), the time complexity would be O(N^2) while the space complexity would be O(1).

(2) Negative value cannot be border: This method is based on such a fact that the negative value cannot be the border element in the maximum subarray, since you remove the negative border out, the sum obviously get larger. So we can scan the array from left to right and keep a current sum over the scanned elements. If the current sum become negative, we set it as zero, if the sum is larger than the global maximum sum, we update the maximum sum. To some extent, this is also could be interpreted as DP approach. The following is the code:

int maxSubArray(int A[], int n) {
    int maxSum = A[0];
    int currentSum = 0;
    for (int i = 0; i < n; ++i) {
        currentSum += A[i];
        if (currentSum > maxSum) maxSum = currentSum;
        if (currentSum < 0)      currentSum = 0;
    }
    return maxSum;
}

(3) DP: Let S[j] denote the maximum sum value among all those subarrays ended at A[j], we have the recursive definition: S[j] = max(A[j], A[j] + S[j - 1]).

(4) Divide and Conquer: divide the array into left and right part, recursively find the maximum sub array in the left and right parts. The third candidate is the subarray cross the mid element (could be calculated in linear time). Then we compare these three result, return the maximum one. The time is T(N) = 2*T(N/2) + O(N), by master’s theroy the time complexity is O(NlogN).

Summary

Different solutions are summarized to solve the LeetCode problem Maximum Subarray including DP, Divide and Conquer, I gave analysis about 4 methods to my knowledge.

Written on May 20, 2013