My Divide and Conquer Solution in Java under instruction of CLRS(O(nlogn))


  • 16
    public class Solution {//divdie and conquer
        public int maxSubArray(int[] nums) {
            return Subarray(nums, 0 ,nums.length -1 );
        }
        public int Subarray(int[] A,int left, int right){
            if(left == right){return A[left];}
            int mid = left + (right - left) / 2;
            int leftSum = Subarray(A,left,mid);// left part 
            int rightSum = Subarray(A,mid+1,right);//right part
            int crossSum = crossSubarray(A,left,right);// cross part
            if(leftSum >= rightSum && leftSum >= crossSum){// left part is max
                return leftSum;
            }
            if(rightSum >= leftSum && rightSum >= crossSum){// right part is max
                return rightSum;
            }
            return crossSum; // cross part is max
        }
        public int crossSubarray(int[] A,int left,int right){
            int leftSum = Integer.MIN_VALUE;
            int rightSum = Integer.MIN_VALUE;
            int sum = 0;
            int mid = left + (right - left) / 2;
            for(int i = mid; i >= left ; i--){
                sum = sum + A[i];
                if(leftSum < sum){
                    leftSum = sum;
                }
            }
            sum = 0;
            for(int j = mid + 1; j <= right; j++){
                sum = sum + A[j];
                if(rightSum < sum){
                    rightSum = sum;
                }
            }
            return leftSum + rightSum;
        }
    }

  • 8
    Y

    I commented on this code and repost it here. Hope I can help someone who has suffering understand this great divide-and-conquer method.

    public class Solution {
    public int maxSubArray(int[] nums) {
        /*
        Divide-and-conquer method.
        The maximum summation of subarray can only exists under following conditions:
        1. the maximum summation of subarray exists in left half.
        2. the maximum summation of subarray exists in right half.
        3. the maximum summation of subarray exists crossing the midpoints to left and right. 
        1 and 2 can be reached by using recursive calls to left half and right half of the subarraies. 
        Condition 3 can be found starting from the middle point to the left,
        then starting from the middle point to the right. Then adds up these two parts and return. 
        
        T(n) = 2*T(n/2) + O(n)
        this program runs in O(nlogn) time
        */
        
        int maxsum = subArray(nums, 0, nums.length-1);
        return maxsum;
    }
    
    private int subArray(int[] A, int left, int right){
        if (left == right){
            //base case
            return A[left];
        }
        int mid = left + (right-left)/2;
        int leftsum = subArray(A, left, mid); //left part of the subarray sum, condition 1
        int rightsum = subArray(A, mid+1, right); //right part of the subarray sum, condition 2
        int middlesum = midSubArray(A, left, mid, right); //cross part of the subarray sum, condition 3
        // System.out.println(leftsum);
        // System.out.println(rightsum);
        // System.out.println(middlesum);
        
        //following if condition will return middlesum if lost the "=" under the conditon of leftsum = rightsum, which may be problematic if leftsum = rightsum < middlesum.
        //for example: [-1, -1, -2, -2]
        if (leftsum >= rightsum && leftsum >= middlesum){
            return leftsum;
        }
        if (rightsum >= leftsum && rightsum >= middlesum){
            return rightsum;
        }
        return middlesum;
    }
    
    private int midSubArray(int[] A, int left, int mid, int right){
        int leftsum = Integer.MIN_VALUE;
        int rightsum = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = mid; i >= left; i--){
            sum += A[i];
            if (leftsum < sum){
                leftsum = sum;
            }
        }
        
        sum = 0;
        for (int j = mid + 1; j <= right; j++){
            sum += A[j];
            if (rightsum < sum){
                rightsum = sum;
            }
        }
        
        return leftsum + rightsum;
    }
    

    }


  • 0
    This post is deleted!

  • 0
    V

    Impressive. But O(nlogn) is worse than the dp O(n) solution , isn't it ?


  • 0

    @vogelkaka
    Yes. But the divide and conquer is more subtle..according to the follow up from the question.


  • 0
    H

    A simpler way of looking at this:

    public int maxSubArray(int[] nums) {
            if(nums.length == 1) return nums[0];
            int m = nums.length / 2;
            int left_MSA = maxSubArray(Arrays.copyOfRange(nums,0,m));
            int right_MSA = maxSubArray(Arrays.copyOfRange(nums,m,nums.length));
    
            int leftMaxSum = Integer.MIN_VALUE, rightMaxSum = Integer.MIN_VALUE;
            int midMaxSum = Integer.MIN_VALUE;
            
            int temp = 0;
            for(int i = m; i < nums.length; i++) {
                temp += nums[i];
                rightMaxSum = Math.max(rightMaxSum, temp);
            }
            temp = 0;
            for(int i = m-1; i >=0; i--) {
                temp += nums[i];
                leftMaxSum = Math.max(leftMaxSum, temp);
            }
            midMaxSum = leftMaxSum + rightMasxSum;
            int interMax = Math.max(left_MSA, right_MSA);
            return Math.max(interMax, midMaxSum);
        }
    

Log in to reply
 

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