For divide and conquer, Why iterating over left part can't go from start to mid but go from mid-1 to the start


  • 0
    R
    public int divide(int[] nums,int start, int end, int tmax){
        if(start>end){
            return Integer.MIN_VALUE;
        }
        int mid=start+(end-start)/2;
        int lmax=divide(nums,start,mid-1,tmax);
        int rmax=divide(nums,mid+1,end,tmax);
        tmax=Math.max(tmax,Math.max(lmax,rmax));
        int sum=0,mlmax=0;
        for (int i = mid-1; i >=start; i--) {// why goes from mid-1 to start. why can't i go from the start to the mid-1
        // for (int i = start; i <=mid-1; i++) {
            sum+=nums[i];
            mlmax=Math.max(mlmax,sum);
        }
        sum=0;
        int mrmax=0;
        for (int i = mid+1; i <=end; i++) {
            sum+=nums[i];
            mrmax=Math.max(mrmax,sum);
        }
        return Math.max(tmax,nums[mid]+mlmax+mrmax);
    }

  • 0
    Y

    @RyanZhu1024
    In loop
    "for (int i = mid-1; i >=start; i--)"
    mlmax the max sum that starts with nums[mid-1].
    If goes from the start to the mid-1, like
    "for (int i = start; i <=mid-1; i++)"
    mlmax will be the max sum that starts with nums[start].


Log in to reply
 

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