Divide & Conquer Java solution.

• ``````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));
}
}
``````

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