Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6

Divide and conquer, recursively divide the array into two parts on the middle point. When combine, start from the joint place of two sub-arrays then assign a left pointer to move to left until arrive the start of left sub-array and right pointer move to right until arrive the end of the right sub-array.

For example,
[2, 3     <-LP | RP->    -2, 4]

In every combine we compute the max value of  left sub array max, right sub array max, and the multiply of the pointers iterated area.

Solution:

``````
class Solution {
public:
int mergeTwoMax(vector<int>& nums, int lMax, int rMax, int l1, int r1, int l2, int r2)
{
int tempLMax = 1 << 31, tempRMax = 1 << 31;
int tempLMin = 1 << 31 - 1, tempRMin = 1 << 31 - 1, sum = 1;
for(int i = r1; i >= l1; --i)
{
sum *= nums[i];
if(tempLMax < sum) tempLMax = sum;
if(tempLMin > sum) tempLMin = sum;
}
sum = 1;
for(int i = l2; i <= r2; ++i)
{
sum *= nums[i];
if(tempRMax < sum) tempRMax = sum;
if(tempRMin > sum) tempRMin = sum;
}
return max(tempLMax * tempRMax,
max(tempLMin * tempRMin,max(lMax, rMax)));
}

int recursiveMax(vector<int>& nums, int l, int r)
{
if(r == l) return nums[l];
if(r - l == 1) return max(nums[l] * nums[r], max(nums[l], nums[r]));

int l1 = l, r1 = (r + l) / 2;
int l2 = r1 + 1, r2 = r;

return mergeTwoMax(nums, recursiveMax(nums, l1, r1),
recursiveMax(nums, l2, r2), l1, r1, l2, r2);
}

int maxProduct(vector<int>& nums) {

if(nums.size() == 0) return 1 << 31;
return recursiveMax(nums, 0, nums.size() - 1);
}
};
``````