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