leetcode152. 乘积最大子数组

分析

minf存储最小值，maxf存储最大值，每次最大值可能由上一个位置转化而来或者当前位置，再或者从最小值（此时为负数得情况）。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector<int>minf(nums),maxf(nums);
        for(int i=1;i<nums.size();i++){
            maxf[i]=max(maxf[i-1]*nums[i],max(minf[i-1]*nums[i],nums[i]));
            minf[i]=min(maxf[i-1]*nums[i],min(minf[i-1]*nums[i],nums[i]));
        }
        return *max_element(maxf.begin(), maxf.end());;
    }
};

优化

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