How to solve "Maximum Subarray" by using the divide and conquer approach ?


  • 21
    C

    I solve this problem in O(n). But the hint says it would be solved by using the divide and conquer approach.
    I cannot figure out how to do it with divide and conquer.
    You guys have ideas?


  • 192
    P

    Step1. Select the middle element of the array.
    So the maximum subarray may contain that middle element or not.

    Step 2.1 If the maximum subarray does not contain the middle element, then we can apply the same algorithm to the the subarray to the left of the middle element and the subarray to the right of the middle element.

    Step 2.2 If the maximum subarray does contain the middle element, then the result will be simply the maximum suffix subarray of the left subarray plus the maximum prefix subarray of the right subarray

    Step 3 return the maximum of those three answer.

    Here is a sample code for divide and conquer solution. Please try to understand the algorithm before look at the code

    class Solution {
    public:
        int maxSubArray(int A[], int n) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            if(n==0) return 0;
            return maxSubArrayHelperFunction(A,0,n-1);
        }
        
        int maxSubArrayHelperFunction(int A[], int left, int right) {
            if(right == left) return A[left];
            int middle = (left+right)/2;
            int leftans = maxSubArrayHelperFunction(A, left, middle);
            int rightans = maxSubArrayHelperFunction(A, middle+1, right);
            int leftmax = A[middle];
            int rightmax = A[middle+1];
            int temp = 0;
            for(int i=middle;i>=left;i--) {
                temp += A[i];
                if(temp > leftmax) leftmax = temp;
            }
            temp = 0;
            for(int i=middle+1;i<=right;i++) {
                temp += A[i];
                if(temp > rightmax) rightmax = temp;
            }
            return max(max(leftans, rightans),leftmax+rightmax);
        }
    };

  • 1
    C

    Great. what is the time complexity?


  • 2
    P

    O(N log N) is the running time


  • 0
    F

    Neat algorithm!


  • 3
    F

    T(n) = 2 * T(n/2) + n
    You can check the Master Theorem to gain time complexity.


  • 0
    F

    What's the algorithm for O(n)..? I can only come up with an O(n^2) one.. and the one below (in the answer) is O(n log n)


  • 0
    S

    For divide and conquer approach, I think O(N log N) is the best time complexity.


  • 0

  • 0
    T

    very good and neat alogirthm


  • 0
    R
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 13
    R

    Here is my answer, not sure if it is a divide and conquer approach. Maybe it is just the normal answer.

    class Solution {
     public: int maxSubArray(int A[], int n) { 
         int s[n]; 
         int max = s[0] = A[0]; 
         for (int i = 1; i < n; i++) {
            s[i] = s[i-1] > 0 ? (A[i] + s[i-1]) : A[i]; 
            max = std::max(max, s[i]); 
         }
         return max;
     }
    };
    

  • 0
    Y

    This is not divide and conquer, but the O(n) solution. Very elegant indeed.


  • 0
    J

    Since its complexity is O(nlgn). It seems that this method is not faster than the O(n) method.


  • 0
    J

    We can reduce the space into O(1), while you use O(n) space. You can just replace the s[n] with a var cur_sum, then in the loop, it should be :
    cur_sum=(cur_sum<0?A[i]:(A[i]+cur_sum));


  • 0
    P

    you are right. It is slower than the linear algorithm


  • 0
    R

    You are right!


  • 6
    C

    Divider and conquer solution can achieve O(N) by returning the max prefix subarray starting with left, max suffix array ending with right, and the sum[left..right].

    My two-pointer solution uses 72ms, this one uses 56ms

    Accepted code:

    int maxSubArray(int A[], int n) {
        if(n == 0)
            return 0;
        else if(n == 1)
            return A[0];
       
        int maxSub = INT_MIN;
        int leftPrefix = INT_MIN, rightSuffix = INT_MIN, all = INT_MIN;
        maxSubArrayHelper(A, 0, n - 1, leftPrefix, rightSuffix, all, maxSub);
        return maxSub;
    }
    
    void maxSubArrayHelper(int A[], int left, int right, int & leftPrefix, int & rightSuffix, int & all, int &maxSub)
    {
        if(left == right)
        {
            leftPrefix = A[left];
            rightSuffix = A[left];
            all = A[left];
            maxSub = max(maxSub, A[left]);
            return;
        }
        
        int middle = (left + right) / 2;
        int leftPrefix1, rightSuffix1, all1, leftPrefix2, rightSuffix2, all2;
        maxSubArrayHelper(A, left, middle, leftPrefix1, rightSuffix1, all1, maxSub);
        maxSubArrayHelper(A, middle + 1, right, leftPrefix2, rightSuffix2, all2, maxSub);
    
        // Use the returned leftPrefix, rightSuffix instead of walling through the elements between left and right
        leftPrefix = max(all1, all1 + leftPrefix2);
        leftPrefix = max(leftPrefix, leftPrefix1);
        rightSuffix = max(all2, all2 + rightSuffix1);
        rightSuffix = max(rightSuffix, rightSuffix2);
        all = all1 + all2;
        maxSub = max(leftPrefix, maxSub);
        maxSub = max(rightSuffix, maxSub);
        maxSub = max(rightSuffix1, maxSub);
        maxSub = max(leftPrefix2, maxSub);
        maxSub = max(rightSuffix1 + leftPrefix2, maxSub);
    }
    

  • 0
    C

    I got an improved version of divide and conquer solution which should achieve O(logN) - http://oj.leetcode.com/discuss/694/how-solve-maximum-subarray-using-divide-and-conquer-approach?show=4084#a4084

    Your comments are very welcome


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.