1. 152

maximum-product-subarray

2. 算法

*DP：O(n)

http://www.cnblogs.com/yanliang12138/p/4634395.html

http://www.cnblogs.com/grandyang/p/4028713.html

3. 代码

http://www.cnblogs.com/grandyang/p/4028713.html



class Solution{
public:
    int maxProduct(vector<int>& nums){
        int n=nums.size();
        if(n==0) return 0;

        int maxIdx=1,minIdx=1;
        int out=nums[0];

        for(int i=0;i<n;i++){
            int oldMax=max(maxIdx,1);
            if(nums[i]>0){
                maxIdx=oldMax*nums[i];
                minIdx*=nums[i];
            }else{
                maxIdx=minIdx*nums[i];
                minIdx=oldMax*nums[i];
            }
            out=max(out,maxIdx);
        }
        return out;
    }
};

3.2 简洁写法

class Solution{
public:
    int maxProduct(vector<int>& nums){
        if(nums.empty())  return 0;
        int res=nums[0],mn=nums[0],mx=nums[0];
        for(int i=1;i<nums.size();++i){
            int tmax=mx,tmin=mn;
            mx=max(max(nums[i],tmax*nums[i]),tmin*nums[i]);
            mn=min(min(nums[i],tmax*nums[i]),tmin*nums[i]);
            res=max(res,mx);
        }

        return res;
    }
};