# Evolve from brute force to optimal, a review of all solutions

• This problem is very similar to maximum subarray, but more tricky.

1. O(n^2) try all subarrays
``````    int maxProduct(vector<int>& nums) {
int n = nums.size(),mp = INT_MIN;
for(int i=0;i<n;i++) {
int cur = 1;
for(int j=i;j<n;j++) mp=max(mp,cur*=nums[j]);
}
return mp;
}
``````
1. O(n) dp, The great idea is from @mzchen
``````    int maxProduct(vector<int>& nums) {
int p = nums[0];
for(int i=1,imax=p,imin=p;i<nums.size();i++) {
if(nums[i]<0) swap(imax,imin);
imax = max(nums[i],imax*nums[i]);
imin = min(nums[i],imin*nums[i]);
p = max(p,imax);
}
return p;
}
``````
1. O(nlogn) Naive divide and conquer
``````    int maxProduct(vector<int>& nums) {
return dac(0,nums.size()-1,nums);
}
int dac(int l, int r, vector<int>& nums) {
if(l==r) return nums[l];
int mid = (l+r)/2, minL=INT_MAX, minR=INT_MAX, maxL=INT_MIN, maxR=INT_MIN, temp =1;
for(int i=mid;i>=l;i--) {
minL = min(minL,temp*=nums[i]);
maxL = max(maxL,temp);
}
temp = 1;
for(int i=mid+1;i<=r;i++) {
minR = min(minR,temp*=nums[i]);
maxR = max(maxR,temp);
}
return max(max(dac(l,mid,nums),dac(mid+1,r,nums)),max(minR*minL,maxR*maxL));
}
``````
1. O(n) divide and conquer
``````    int maxProduct(vector<int>& nums) {
int maxl, maxr, minl, minr, p;
return dac(0,nums.size()-1,maxl,maxr,minl,minr,p,nums);
}
int dac(int l, int r, int& maxl, int& maxr, int& minl, int& minr, int& p,vector<int>& nums) {
if(l==r) return maxl=maxr=minl=minr=p=nums[l];
int mid = (l+r)/2, lmaxl,lmaxr,lminl,lminr,lp,rmaxl,rmaxr,rminl,rminr,rp;
int mp = max(dac(l,mid,lmaxl,lmaxr,lminl,lminr,lp,nums),dac(mid+1,r,rmaxl,rmaxr,rminl,rminr,rp,nums));
maxl = max(lmaxl,max(lp*rmaxl,lp*rminl));
maxr = max(rmaxr,max(rp*lmaxr,rp*lminr));
minl = min(lminl,min(lp*rminl,lp*rmaxl));
minr = min(rminr, min(rp*lminr,rp*lmaxr));
p = lp*rp;
return max(mp,max(lmaxr*rmaxl,lminr*rminl));
}
``````

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