[C++] LeetCode 152. 乘积最大子序列

题目

找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

例如， 给定序列

[2,3,-2,4]

，

其中乘积最大的子序列为

[2,3]

其乘积为

6

。

题解

这题需要考虑到负数，用动态规划即可，但是要考虑到最大正数和最小负数，因为负数乘以最小负数可能为最大数，数组

maxnum[i]

和

minnum[i]

分别表示以

i

为结尾的数组最大乘积和最小乘积。

代码

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n=nums.size();
        vector<int> maxnum(n,),minnum(n,);
        int maxres=INT_MIN;
        for(int i=;i<n;i++){
            if(i==){
                maxnum[i]=nums[i];
                minnum[i]=nums[i];
            }
            else{
                maxnum[i]=max(maxnum[i-]*nums[i],max(minnum[i-]*nums[i],nums[i]));
                minnum[i]=min(maxnum[i-]*nums[i],min(minnum[i-]*nums[i],nums[i]));
            }
            maxres=max(maxres,maxnum[i]);
        }
        return maxres;
    }
};