题目链接 · 灵神原题解（署名来源）

本题是 53. 最大子数组和 的乘法版本，推荐先完成 53 题。

寻找子问题

例如 $\mathit{\text{nums}}=[-2,1,-3,4]$，讨论右端点为 $\mathit{\text{nums}}[3]=4$ 的子数组的最大乘积：

• $4$ 单独组成一个子数组。
• $4$ 和前面的子数组拼起来，也就是在右端点为 $\mathit{\text{nums}}[2]=-3$ 的乘积最大子数组之后添加 $4$。

又例如 $\mathit{\text{nums}}=[-2,1,-3,-4]$，讨论右端点为 $\mathit{\text{nums}}[3]=-4$ 的子数组的最大乘积：

• $-4$ 单独组成一个子数组。
• $-4$ 和前面的子数组拼起来，由于 $-4$ 是负数，要想得到最大的乘积，根据负负得正，我们可以在右端点为 $\mathit{\text{nums}}[2]=-3$ 的乘积最小子数组之后添加 $-4$。

状态定义与状态转移方程

上面两个例子启发我们，需要在遍历 $\mathit{\text{nums}}$ 的同时，维护两个信息：

• 右端点下标为 $i$ 的子数组的最大乘积，记作 $f_{\mathit{\text{max}}}[i]$。
• 右端点下标为 $i$ 的子数组的最小乘积，记作 $f_{\mathit{\text{min}}}[i]$。

设 $x=\mathit{\text{nums}}[i]$，分类讨论：

• $x$ 单独组成一个子数组，那么 $f_{\mathit{\text{max}}}[i]=x$。
• $x$ 和前面的子数组拼起来，也就是在右端点下标为 $i-1$ 的乘积最大子数组之后添加 $x$，那么 $f_{\mathit{\text{max}}}[i]=f_{\mathit{\text{max}}}[i-1]\cdot x$；也可以在右端点下标为 $i-1$ 的乘积最小子数组之后添加 $x$，那么 $f_{\mathit{\text{max}}}[i]=f_{\mathit{\text{min}}}[i-1]\cdot x$。把这两种都算一下，这样我们就无需判断 $x$ 到底是正还是负了。

三种情况取最大值，得

$$f_{\mathit{\text{max}}}[i]=max(f_{\mathit{\text{max}}}[i-1]\cdot x,f_{\mathit{\text{min}}}[i-1]\cdot x,x)$$

同理得

$$f_{\mathit{\text{min}}}[i]=min(f_{\mathit{\text{max}}}[i-1]\cdot x,f_{\mathit{\text{min}}}[i-1]\cdot x,x)$$

由于以 $\mathit{\text{nums}}[0]$ 为右端点的子数组乘积只能是 $\mathit{\text{nums}}[0]$，所以初始值为 $f_{\mathit{\text{max}}}[0]=f_{\mathit{\text{min}}}[0]=\mathit{\text{nums}}[0]$。这是一种初始化的方法，下文会讲另外一种。

答案为 $max(f_{\mathit{\text{max}}})$。

写法一

Python 解法1

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        f_max = [0] * n
        f_min = [0] * n
        f_max[0] = f_min[0] = nums[0]
        for i in range(1, n):
            x = nums[i]
            # 把 x 加到右端点为 i-1 的（乘积最大/最小）子数组后面，
            # 或者单独组成一个子数组，只有 x 一个元素
            f_max[i] = max(f_max[i - 1] * x, f_min[i - 1] * x, x)
            f_min[i] = min(f_max[i - 1] * x, f_min[i - 1] * x, x)
        return max(f_max)

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> f_max(n), f_min(n);
        f_max[0] = f_min[0] = nums[0];
        for (int i = 1; i < n; i++) {
            int x = nums[i];
            // 把 x 加到右端点为 i-1 的（乘积最大/最小）子数组后面，
            // 或者单独组成一个子数组，只有 x 一个元素
            f_max[i] = max({f_max[i - 1] * x, f_min[i - 1] * x, x});
            f_min[i] = min({f_max[i - 1] * x, f_min[i - 1] * x, x});
        }
        return ranges::max(f_max);
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\mathit{\text{nums}}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

写法二（空间优化）

由于计算 $f_{\mathit{\text{max}}}[i]$ 和 $f_{\mathit{\text{min}}}[i]$ 只会用到 $f_{\mathit{\text{max}}}[i-1]$ 和 $f_{\mathit{\text{min}}}[i-1]$，不会用到更早的状态，所以可以用两个变量 $f_{\mathit{\text{max}}}$ 和 $f_{\mathit{\text{min}}}$ 滚动计算。具体请看视频讲解 动态规划入门：从记忆化搜索到递推。

状态转移方程简化为：

$$\begin{array}{rl}{f}_{\mathit{\text{max}}}& =max(f_{\mathit{\text{max}}}\cdot x,f_{\mathit{\text{min}}}\cdot x,x)\\ f_{\mathit{\text{min}}}& =min(f_{\mathit{\text{max}}}\cdot x,f_{\mathit{\text{min}}}\cdot x,x)\end{array}$$

注意这两个式子要同时计算。

代码实现时，可以初始化 $f_{\mathit{\text{max}}}=f_{\mathit{\text{min}}}=1$，因为 $1$ 乘以 $\mathit{\text{nums}}[0]$ 等于 $\mathit{\text{nums}}[0]$，这样我们可以从下标 $0$ 开始遍历 $\mathit{\text{nums}}$，代码写起来更简单。

Python 解法3

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ans = -inf  # 注意答案可能是负数
        f_max = f_min = 1
        for x in nums:
            f_max, f_min = max(f_max * x, f_min * x, x), \
                           min(f_max * x, f_min * x, x)
            ans = max(ans, f_max)
        return ans

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int ans = INT_MIN; // 注意答案可能是负数
        int f_max = 1, f_min = 1;
        for (int x : nums) {
            int mx = f_max;
            f_max = max({f_max * x, f_min * x, x});
            f_min = min({mx * x, f_min * x, x});
            ans = max(ans, f_max);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\mathit{\text{nums}}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。

写法三

Python 解法5

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ans = -inf
        f_max = f_min = 1
        for x in nums:
            if x < 0:
                # 下面与 x 相乘后，最大的正数变成最小的负数，最小的负数变成最大的正数
                # 提前交换，这样可以把 x < 0 和 x >= 0 的情况合并，合并后，计算 max 和 min 可以少一项
                f_max, f_min = f_min, f_max
            f_max = max(f_max * x, x)
            f_min = min(f_min * x, x)
            ans = max(ans, f_max)
        return ans

C++ 解法5

// C++ 版待补充

C++ 解法6

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int ans = INT_MIN;
        int f_max = 1, f_min = 1;
        for (int x : nums) {
            if (x < 0) {
                // 下面与 x 相乘后，最大的正数变成最小的负数，最小的负数变成最大的正数
                // 提前交换，这样可以把 x < 0 和 x >= 0 的情况合并，合并后，计算 max 和 min 可以少一项
                swap(f_max, f_min);
            }
            f_max = max(f_max * x, x);
            f_min = min(f_min * x, x);
            ans = max(ans, f_max);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\mathit{\text{nums}}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。

变形题

把子数组改成子序列，要怎么做？

• 2708. 一个小组的最大实力值

更多相似题目，见下面动态规划题单中的「§1.3 最大子数组和」。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府