Divide & Conquer CLRS Implementation O(nlgn)


  • 0
    P
    // Divide and Conquer Solution From CLRS
        
        public int maxSubArray(int[] nums) {
            
            if(nums.length == 0 || nums == null){
                return 0;
            }
            return divideAndConquer(nums, 0, nums.length - 1);
        }
        
        private int divideAndConquer (int[] nums, int l, int r){
            
            if (l == r){
                return nums[l];
            }
            
            int mid = l + (r - l) / 2;
            
            return Math.max(divideAndConquer(nums, l, mid), 
                       Math.max(divideAndConquer(nums, mid + 1, r),
                       maxSubArrayCross(nums, l, mid, r)));
        }
        private int maxSubArrayCross(int[] nums, int l, int mid, int r){
            
            int leftSum = Integer.MIN_VALUE;
            int rightSum = Integer.MIN_VALUE;
            int sum = 0;
    
            for(int i = mid; i >= l ; i--){
                sum = sum + nums[i];
                if(leftSum < sum){
                    leftSum = sum;
                }
            }
            
            sum = 0;
            for(int i = mid + 1; i <= r; i++){
                sum = sum + nums[i];
                if(rightSum < sum){
                    rightSum = sum;
                }
            }
            return leftSum + rightSum;
        }
    

Log in to reply
 

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