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


  • 0

    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));
        }
    

Log in to reply
 

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