LeetCode HOT100 - 乘积最大子数组

如果是和最大，那么直接一直加上去和 0 取个 max 好了，因为正值对后续一定是正贡献

现在考虑积，是不是也是类似

部分类似，如果全部都是正值，那么是类似的

但是有负值

负数的影响是什么呢，就是这里是小的，但是下次再乘个负数它就正了

所以这里要同时维护最小值和最大值

当然只维护两个元素自然也可以

但这里用 dp 数组

dp[i][0] 表示以 i 结尾，且用了 i 的最小值
dp[i][1] 就是最大值

之所以要用 i ，是因为后面更新是要和前面连着的，所以更新 i 时 i -1 必须用上，因此状态设计时 i 是被使用了的

每次更新只和前一个元素有关

class Solution {
public:
    int maxProduct(vector<int>& a) {
        int n = a.size();
        if (n == 1) {
            return a[0];
        }
        int ans = a[0];
        vector<array<int, 2>> dp(n);
        dp[0][1] = max(1, a[0]);
        dp[0][0] = min(1, a[0]);
        for (int i = 1; i < n; i++) {
            dp[i][0] = min({dp[i - 1][0] * a[i], dp[i - 1][1] * a[i], 1});
            dp[i][1] = max({dp[i - 1][0] * a[i], dp[i - 1][1] * a[i], 1});
            ans = max({dp[i - 1][0] * a[i], dp[i - 1][1] * a[i], ans});
        }
        return ans;
    }
};