给你一个整数数组
nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。
请注意，一个只包含一个元素的数组的乘积是这个元素的值。
示例 1:
示例 2:
这道题看起来像 Maximum Subarray 的变体，但乘法比加法更麻烦。加法里，一个负数只会让和变小；乘法里，负数会翻转符号，一个很小的负数乘上另一个负数，可能瞬间变成最大的正数。
这就是这道题的核心观察：以当前位置结尾的最大乘积，不只依赖之前的最大乘积，也依赖之前的最小乘积。
因为当前数
num 可能是负数。一旦 num < 0，之前的最小乘积乘上它，反而可能变成最大乘积。解法一：动态规划状态压缩
定义两个状态，同时维护最大乘积和最小乘积：
为什么状态必须是“以当前位置结尾”？因为子数组必须连续。我们每次处理
num 时，只有三种选择：- 把
num接在之前最大乘积子数组后面；
- 把
num接在之前最小乘积子数组后面；
- 从
num自己重新开始一个子数组。
因此转移是：
然后用
newMax 更新全局答案。这个写法自然处理了正数、负数和
0 当
num == 0 时，newMax 和 newMin 都会变成 0；下一个数可以通过“从自己重新开始”重新建立乘积。因此不需要单独重置为 1。Walk Through Example
以 nums = [-1, -2, -3, -4] 为例。
看到
-1 时，最大和最小都是 -1。看到 -2 时，-1 * -2 = 2，最大乘积变成 2，最小乘积是 -2。看到 -3 时，之前的最小乘积 -2 乘以 -3 得到 6，所以最大乘积变成 6；看到 -4 时，之前的最小乘积 -6 乘以 -4 得到 24，最终答案是 24。这个例子说明，最小乘积不是废信息，它可能在遇到负数时翻身成为最大值。
这个写法状态定义清楚，转移稳定，也不需要额外处理
0。复杂度分析
- 时间复杂度：
O(n)，只遍历数组一次。
- 空间复杂度：
O(1)，只维护几个变量。
解法二：重置版 DP —— 遇到 0 后用 1 重新开始
另一种常见写法是把
curMax 和 curMin 初始化为 1，遇到 0 时把它们重置为 1。这背后的 intuition 是：
0 会切断连续乘积，任何跨过 0 的子数组乘积都会变成 0，所以后面的子数组应该重新开始。需要注意两点：
- 答案不能初始化为
0，因为数组可能全是负数，比如[-1]，正确答案是-1。所以一般写res = max(nums)
- 更新
curMin时必须使用旧的curMax，不能用已经更新后的curMax。因此需要临时变量保存旧值。
复杂度分析
- 时间复杂度：
O(n)。
- 空间复杂度：
O(1)。
解法三：前缀积
还有一种思路从前缀积出发。对于没有
0 的一段数组，子数组乘积可以表示成两个前缀积的商：如果当前前缀积是正数，想让结果尽可能大，就希望除以前面最小的正前缀积。
如果当前前缀积是负数，想让结果变成最大的正数，就希望除以前面最大的负前缀积。
所以需要维护：
curProduct = 当前段的前缀乘积
minPositive = 前面最小的正前缀积
maxNegative = 前面最大的负前缀积
遇到
0 时，当前连续段被切断，需要重置这些状态。这个思路和“最大 / 最小乘积 DP”本质上很接近，只是从除法和前缀积角度解释。
它的核心是通过前缀积和符号信息定位最优子数组，本质上仍然是在维护一段连续区间内的极值状态。
复杂度分析
- 时间复杂度：
O(n)。
- 空间复杂度：
O(1)。
解法四：正反两次扫描
还有一种非常巧妙的写法：从左到右扫一遍，再从右到左扫一遍，取所有前缀积中的最大值。
考虑一段不含
0 的连续数组：- 如果负数个数是偶数，那么整段乘积最大，全部乘起来即可；
- 如果负数个数是奇数，那么最大乘积一定来自“去掉第一个负数之前的前缀”或者“去掉最后一个负数之后的后缀”。
从左到右扫，可以覆盖“去掉左侧前缀”的情况；从右到左扫，可以覆盖“去掉右侧后缀”的情况。
遇到
0 时，乘积重置，因为 0 会切断连续子数组。所以，假设一段数组没有
0- 如果负数个数为偶数，整段乘积会在某次扫描中被记录到。
- 如果负数个数为奇数，最大乘积要么丢掉左边到第一个负数为止的部分，要么丢掉右边到最后一个负数为止的部分；
正向扫描和反向扫描刚好分别覆盖这两种情况。
复杂度分析
- 时间复杂度：
O(n)。
- 空间复杂度:
O(1)。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode152-最大乘积子数组
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode148] 链表排序
下一篇
[Leetcode 160] 相交链表