乘积最大子数组

解题思路

一开始以为和最长子序列一样，使用一个dp[n]记录以nums[n]为末尾元素的，最大子序列和。后来发现还有负负得正的情况。所以使用dp_min维护最小序列乘积，最后状态转移的时候，需要判断三个值得大小。
dp_max[i] = max({dp_max[i-1]dp_max[i], dp_min[i-1]dp_max[i], dp_max[i]});

代码

cpp

class Solution {
public:

    int maxProduct(vector<int>& nums) {
        vector<int> dp_max(nums);
        vector<int> dp_min(nums);

        int max_count = dp_max[0];
        


        for(int i=1; i<nums.size(); i++){
            dp_max[i] = max({dp_max[i-1]*dp_max[i], dp_min[i-1]*dp_max[i], dp_max[i]});
            dp_min[i] = min({dp_min[i-1]*dp_min[i], dp_max[i-1]*dp_min[i], dp_min[i]});

            max_count= max(dp_max[i], max_count);

        }
        return max_count;
    }
};