当前位置的最优解未必是由前一个位置的最优解转移得到的。讨论正负

$\begin{aligned}f_{\max }(i) &=\max {i=1}^n\left\{f{\max }(i-1) \times a_i, f_{\min }(i-1) \times a_i, a_i\right\} \\f_{\min }(i) &=\min {i=1}\left\{f{\max }(i-1) \times a_i, f_{\min }(i-1) \times a_i, a_i\right\}\end{aligned}$

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp_min(n, 0), dp_max(n, 0);
        dp_min[0] = nums[0], dp_max[0] = nums[0];
        int res = nums[0];
        for (int i = 1; i < n; i ++) {
            dp_max[i] = max(nums[i], max(dp_max[i - 1] * nums[i], dp_min[i - 1] * nums[i]));
            dp_min[i] = min(nums[i], min(dp_min[i - 1] * nums[i], dp_max[i - 1] * nums[i]));
            res = max(res, dp_max[i]);
        }
        return res;
    }
};

空间优化O(1)

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxval, minval, res;
        maxval = minval = res = nums[0];
        for (int i = 1; i < nums.size(); i ++) {
            int x = maxval, y = minval; // 注意这一句
            maxval = max(nums[i], max(x * nums[i], y * nums[i]));
            minval = min(nums[i], min(x * nums[i], y * nums[i]));
            res = max(res, maxval);
        }
        return res;
    }
};

要求连续