public int maxSubArrayRec(int[] nums, int i, int j) {
if(i==j)
return nums[i];
int mid = (i + j) / 2;
int leftMax = maxSubArrayRec(nums,i,mid);
int rightMax = maxSubArrayRec(nums,mid+1,j);
int subMax = Math.max(leftMax,rightMax);
int leftContiguousMax = nums[mid];
int leftSum = nums[mid];
for(int k=mid1; k>=i; k) {
leftSum += nums[k];
if(leftSum > leftContiguousMax)
leftContiguousMax = leftSum;
}
if(leftContiguousMax <= 0)
return subMax;
int rightContigousMax = nums[mid+1];
int rightSum = nums[mid+1];
for(int k=mid+2; k<=j; k++) {
rightSum += nums[k];
if(rightSum > rightContigousMax)
rightContigousMax = rightSum;
}
if(rightContigousMax <= 0)
return subMax;
return Math.max(subMax,leftContiguousMax+rightContigousMax);
}
public int maxSubArray(int[] nums) {
return maxSubArrayRec(nums,0,nums.length1);
}
Easy divideandconquer solution in Java (for those wants to practice!)


Great code ! Thanks for your sharing !
We first compute left side max sum, then compute right side sum, then for the possibility that the max subarray could be in the middle, just add maximum continuous subarray from left to mid, and maximum continuous subarray from mid + 1 to right. Then return the max value of (left, right, middle) !