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;

    }

};