Easy divide-and-conquer solution in Java (for those wants to practice!)


  • 1
    public int maxSubArrayRec(int[] nums, int i, int j) {
        if(i==j)
            return nums[i];
        int mid = (i + j) / 2;
        int leftMax = maxSubArrayRec(nums,i,mid);
        int rightMax = maxSubArrayRec(nums,mid+1,j);
        int subMax = Math.max(leftMax,rightMax);
        
        int leftContiguousMax = nums[mid];
        int leftSum = nums[mid];
        for(int k=mid-1; k>=i; k--) {
            leftSum += nums[k];
            if(leftSum > leftContiguousMax)
                leftContiguousMax = leftSum;
        }
        
        if(leftContiguousMax <= 0)
            return subMax;
        
        int rightContigousMax = nums[mid+1];
        int rightSum = nums[mid+1];
        for(int k=mid+2; k<=j; k++) {
            rightSum += nums[k];
            if(rightSum > rightContigousMax)
                rightContigousMax = rightSum;
        }
        
        if(rightContigousMax <= 0)
            return subMax;
        
        return Math.max(subMax,leftContiguousMax+rightContigousMax);
    }
    
    public int maxSubArray(int[] nums) {
        return maxSubArrayRec(nums,0,nums.length-1);
    }

  • 0
    V

    Great code ! Thanks for your sharing !

    We first compute left side max sum, then compute right side sum, then for the possibility that the max subarray could be in the middle, just add maximum continuous subarray from left to mid, and maximum continuous subarray from mid + 1 to right. Then return the max value of (left, right, middle) !


Log in to reply
 

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