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