# Simple Divide and Conquer solution Java (answer for the more practice)

• The idea is simple, every time we divide the array "nums" into two parts :
1 . left part: (0 , mid) 2 . right part: (mid+1 , nums.length-1)
max value may come from the following three conditions
1 .left part 2. right part 3. cross part ( i , j ) (0 <= i <= mid and mid+1 <= j <= num.length-1)
for the left part and right part, just using recurrence and for the cross part, using a loop.

``````public class Solution {
public int maxSubArray(int[] nums) {
if(nums == null || nums.length == 0) {
return 0;
}
return dfshelper(nums , 0 , nums.length-1);
}

protected int dfshelper(int[] nums , int left , int right) {
if(left == right) {
return nums[left];
}
int mid = left + (right - left) / 2;
int leftmax = dfshelper(nums , left , mid);//   divide part
int rightmax = dfshelper(nums , mid+1 , right); //  divide part
int lmax = Integer.MIN_VALUE;
int rmax = Integer.MIN_VALUE;
int leftsum = 0;
int rightsum = 0;
for(int i = mid ; i >= left ; i--) { //  conquer part
leftsum += nums[i];
lmax = Math.max(lmax , leftsum);
}
for(int i = mid+1 ; i <= right ; i++) { //  conquer part
rightsum += nums[i];
rmax = Math.max(rmax , rightsum);
}
int crossmax = lmax + rmax; //  conquer part
return Math.max(crossmax , Math.max(leftmax , rightmax));   //  combine part
}
``````

}

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