Sharing my divide and conquer solution using C++


  • 2
    Z
    int maxSubArray(int A[], int n) {
        return divideAndConquer(A, 0, n - 1);
    }
    int divideAndConquer(int A[], int left, int right){
        if(left == right){
            return A[left];
        }
        if(left > right){
            return INT_MIN;
        }
        int mid = left + (right - left) / 2;
        int maxLeft = 0;
        int sum = 0;
        for(int i = mid - 1; i >= left; i--){
            sum += A[i];
            maxLeft = max(maxLeft, sum);
        }
        int maxRight = 0;
        sum = 0;
        for(int i = mid + 1; i <= right; i++){
            sum += A[i];
            maxRight = max(maxRight, sum);
        }
        int maxSumWithMid = maxLeft + A[mid] + maxRight;
        return max(maxSumWithMid, max(divideAndConquer(A, left, mid - 1), divideAndConquer(A, mid + 1, right)));
    }

  • 0
    L

    Sharing my java divide and conquer code

       public class Solution {
            public int maxSubArray(int[] A) {
                return helper(A, 0, A.length);
            }
            
            public int helper(int[] A, int start, int end){
                if(start==end-1) return A[start];
                int middle = (start + end) / 2;
                int leftSub = helper(A, start, middle);
                int rightSub = helper(A, middle, end);
                int i,leftcut=-1,rightcut=-1,leftsum=0,rightsum=0,leftmax=-Integer.MAX_VALUE,rightmax=-Integer.MAX_VALUE;
                for(i=middle;i<end;i++){
                    rightsum += A[i];
                    if(rightsum>=0 && rightsum>rightmax){
                        rightmax = rightsum;
                        rightcut = i;
                    }
                }
                for(i=middle-1;i>=start;i--){
                    leftsum += A[i];
                    if(leftsum>=0 && leftsum>leftmax){
                        leftmax = leftsum;
                        leftcut = i;
                    }
                }
                
                int sub;
                if(leftSub>rightSub){
                    sub = leftSub;
                }
                else{
                    sub = rightSub;
                }
                if(leftcut==-1 || rightcut==-1){
                    return sub;
                }
                else{
                    if(sub>leftmax+rightmax){
                        return sub;    
                    }
                    else{
                        return leftmax + rightmax;
                    }
                }
            }
        }

  • 0
    O

    Does divide n conquer act like a divide n conquer style dp?


  • 0

    I think the run time is O(n) + O(n/2) + O(n/4)...+O(1), it's d&c, but not more subtle.


Log in to reply
 

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