Divide & Conquer Java solution.


  • 0
    O
    public class Solution {
        public int maxSubArray(int[] nums) {
            if(nums.length == 1) return nums[0];
            return maxSubArrayHelper(nums, 0, nums.length-1);
        }
        public int maxSubArrayHelper(int[] nums, int start, int end) {
            if(start >= end) return nums[start];
            int mid   = (end-start)/2;
            int left  = maxSubArrayHelper(nums, start, start+mid);
            int right = maxSubArrayHelper(nums, start+mid+1, end);
            int cros  = maxCrossingSubArray(nums, start, start+mid, end);
            return Math.max(cros, Math.max(left, right));
        }
        public int maxCrossingSubArray(int[] nums, int start, int mid, int end) {
        	if (start == end) return nums[start];
        	int left = Integer.MIN_VALUE;
            int sum = 0;
            if(start <= mid) {
    	        for(int i = mid-1; i >= start; i--) {
    	        	sum += nums[i];
    	        	if (sum > left) left = sum;
    	        }
        	}
            int right = Integer.MIN_VALUE;
            if (mid <= end) {
    	        sum = 0;
    	        for(int i = mid; i <= end; i++) {
    	        	sum += nums[i];
    	        	if (sum > right) right = sum;
    	        }
            }
            if(left == Integer.MIN_VALUE) return right;
            if(right == Integer.MIN_VALUE) return left;
            return Math.max(left+right, Math.max(left,  right)); 
        }
    }
    

Log in to reply
 

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