# C++ solution by using divide and conquer

• The idea behind this was exactly borrowed from the similar problem Maximum Subarray, and porker2008 had made a great explanation

Thought this approach is not effective(only beat 8% cppsubmisssions ), it gives us another way to think.

``````class Solution {
public:
int maxProduct(vector<int>& a) {
return maxProductHelper(a, 0, a.size()-1);
}
int maxProductHelper(vector<int>& a, int left, int right) {
if (right == left) return a[right];
// use divide and conquer
int middle = (left + right) / 2;
// case 1: max product subarray contains the middle element
int leftMax = a[middle];
int leftMin = a[middle];
int rightMax = a[middle+1];
int rightMin = a[middle+1];
int i;
int tmp = a[middle];
for(i=middle-1; i>=left; i--) {
tmp *= a[i];
if (tmp>leftMax) leftMax = tmp;
if (tmp<leftMin) leftMin = tmp;
}
tmp = a[middle+1];
for(i=middle+2; i<=right; i++) {
tmp *= a[i];
if(tmp>rightMax) rightMax = tmp;
if(tmp<rightMin) rightMin = tmp;
}
int middleAns = max(leftMax*rightMax, leftMin*rightMin);
// case 2.1: not contain the middle element, subarray elements all in left
int leftAns = maxProductHelper(a, left, middle);
// case 2.2: not contain the middle element, subarray elements all in right
int rightAns = maxProductHelper(a, middle+1, right);
// calculate above 3 cases and return the maximum one
return max(max(leftAns, rightAns), middleAns);
}
};
``````

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