Clean Java Divide and Conquer O(n) 3ms


  • 0
    S

    For each subproblem , we want to keep track of 4 variables:

    1. max_sum_from_left: the largest sum of continguous subarray starting from the leftmost position

    2. max_sum_from_right: the largest sum of continguous subarray ending at the rightmost position

    3. sum_all: the sum over all the current array

    4. max_sum: current largest sum of any contiguous array

    (1). (2) are used to merge two subproblems because if we divide an array, say a[0:n-1], into a[0:k-1] and a[k, n-1], we might find the largest subarray across the two, say a[k-i, k +j];

    max_sum of a[0, n-1] = max( max_sum of a[0:k-1], max_sum of a[k, n-1], max_sum_from_right of a[0:k-1] + max_sum_from_left of a[k, n-1] );

    (3) is used to update (1) and (2) when merging the two subproblems, see code below for update rule.

    (4) is used to record the current max value, as in every other solution.

     public class Solution {
    	class Info{                                 //Wrapper used for passing reference of primitive variables
    		public int max_sum_from_left;           //the largest sum of continguous subarray starting from the leftmost position
    		public int max_sum_from_right;          //the largest sum of continguous subarray starting from the rightmost position
    		public int sum_all;                     //the sum over all the array
    		public int max_sum;                     //current larget sum of any contiguous array
    	}
        public void maxSubArrayHelper(int[] nums, int left, int right, Info info)
        {
            if(left == right){
                info.max_sum_from_left = nums[left];
                info.max_sum_from_right  = nums[left];
                info.sum_all = nums[left];
                info.max_sum = nums[left];
                return;
            }
        
            int middle = (left + right) / 2;
            Info info1 = new Info();
            Info info2 = new Info();
            maxSubArrayHelper(nums, left, middle, info1);
            maxSubArrayHelper(nums, middle + 1, right, info2);
        
            info.max_sum_from_left = Math.max(info1.max_sum_from_left, info1.sum_all + info2.max_sum_from_left);
            info.max_sum_from_right = Math.max(info2.max_sum_from_right, info2.sum_all + info1.max_sum_from_right);
            info.sum_all = info1.sum_all + info2.sum_all;
            info.max_sum = Math.max(info1.max_sum, info2.max_sum);
            info.max_sum = Math.max(info.max_sum, info1.max_sum_from_right + info2.max_sum_from_left);
            return;
        }
        public int maxSubArray(int[] nums) {
    	    if(nums.length == 0)	return 0;
    	    if(nums.length == 1)	return nums[0];
    	    Info info = new Info();
    	    info.max_sum = Integer.MIN_VALUE;
    	    maxSubArrayHelper(nums, 0, nums.length - 1, info);
    	    return info.max_sum;
        }

Log in to reply
 

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