Simple Divide and Conquer solution Java (answer for the more practice)


  • 0

    The idea is simple, every time we divide the array "nums" into two parts :
    1 . left part: (0 , mid) 2 . right part: (mid+1 , nums.length-1)
    max value may come from the following three conditions
    1 .left part 2. right part 3. cross part ( i , j ) (0 <= i <= mid and mid+1 <= j <= num.length-1)
    for the left part and right part, just using recurrence and for the cross part, using a loop.

    public class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        return dfshelper(nums , 0 , nums.length-1);
    }
    
    protected int dfshelper(int[] nums , int left , int right) {
        if(left == right) {
            return nums[left];
        }
        int mid = left + (right - left) / 2;
        int leftmax = dfshelper(nums , left , mid);//   divide part
        int rightmax = dfshelper(nums , mid+1 , right); //  divide part
        int lmax = Integer.MIN_VALUE;
        int rmax = Integer.MIN_VALUE;
        int leftsum = 0;
        int rightsum = 0;
        for(int i = mid ; i >= left ; i--) { //  conquer part
            leftsum += nums[i];
            lmax = Math.max(lmax , leftsum);
        }
        for(int i = mid+1 ; i <= right ; i++) { //  conquer part
            rightsum += nums[i];
            rmax = Math.max(rmax , rightsum);
        }
        int crossmax = lmax + rmax; //  conquer part
        return Math.max(crossmax , Math.max(leftmax , rightmax));   //  combine part
     }
    

    }


Log in to reply
 

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