# 3ms Java Divide-and-Conquer Solution beats 85%

• ``````public class Solution {

public int maxProductRec(int[] nums, int i, int j) {
if(i==j)
return nums[i];
int mid = (i+j)/2;
int leftMax = maxProductRec(nums,i,mid);
int rightMax = maxProductRec(nums,mid+1,j);
int subMax = Math.max(leftMax,rightMax);

int leftContiguousMax = nums[mid];
int leftContiguousMin = nums[mid];
int leftProduct = nums[mid];
for(int k=mid-1; k>=i; k--) {
leftProduct *= nums[k];
leftContiguousMax = leftProduct > leftContiguousMax ? leftProduct : leftContiguousMax;
leftContiguousMin = leftProduct < leftContiguousMin ? leftProduct : leftContiguousMin;
}

int rightContiguousMax = nums[mid+1];
int rightContiguousMin = nums[mid+1];
int rightProduct = nums[mid+1];
for(int k=mid+2; k<=j; k++) {
rightProduct *= nums[k];
rightContiguousMax = rightProduct > rightContiguousMax ? rightProduct : rightContiguousMax;
rightContiguousMin = rightProduct < rightContiguousMin ? rightProduct : rightContiguousMin;
}

int crossMax = Math.max(leftContiguousMax*rightContiguousMax, leftContiguousMin*rightContiguousMin);

return Math.max(subMax, crossMax);
}

public int maxProduct(int[] nums) {
return maxProductRec(nums, 0, nums.length-1);
}
}``````

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