152. 乘积最大子数组

题目链接（中等）

题目描述

给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32 位 整数。

请注意，一个只包含一个元素的数组的乘积是这个元素的值。

数据范围：

• 1 <= nums.length <= 2 * 10^4
• -10 <= nums[i] <= 10
• nums 的任何子数组的乘积都保证是一个 32 位整数

示例

示例 1：

输入： nums = [2,3,-2,4]
输出： 6
解释： 子数组 [2,3] 有最大乘积 6。

示例 2：

输入： nums = [-2,0,-1]
输出： 0
解释： 结果不能为 2，因为 [-2,-1] 不是子数组。

核心思路

如果直接套用「53. 最大子数组和」的 DP：

$$f_{\max}(i) = \max(f_{\max}(i-1) \cdot a_i,\ a_i)$$

这是错误的。因为乘法里负数 × 负数 = 正数，当前位置的最优解未必由前一个位置的最优解转移而来。

反例：nums = [5, 6, -3, 4, -3]

按上面的 DP 走一遍：

• f_max(0) = 5
• f_max(1) = 30
• f_max(2) = max(30 × -3, -3) = -3
• f_max(3) = max(-3 × 4, 4) = 4
• f_max(4) = max(4 × -3, -3) = -3

最终答案是 30，但真正的答案是整个数组的乘积 5 × 6 × (-3) × 4 × (-3) = 1080。

问题在于：f_max(2) = -3 时，它丢掉了「-3 前面累积了一个很大的正数」这个信息。等到后面再遇到一个负数，本来可以负负得正，但这条路已经断了。

结论：只维护「以当前位置结尾的最大乘积」不够，还要维护「最小乘积」。因为一个很小的负数，遇到下一个负数，可能翻转成很大的正数。

---

方法一：动态规划（维护最大值和最小值）

思路及解法

定义两个状态：

• f_max(i)：以 nums[i] 结尾的最大子数组乘积；
• f_min(i)：以 nums[i] 结尾的最小子数组乘积。

转移方程：

$$f_{\max}(i) = \max(f_{\max}(i-1) \cdot a_i,\ f_{\min}(i-1) \cdot a_i,\ a_i)$$ $$f_{\min}(i) = \min(f_{\max}(i-1) \cdot a_i,\ f_{\min}(i-1) \cdot a_i,\ a_i)$$

为什么最小值也要参与最大值转移？

• 当前 a_i 是正数时：f_max(i-1) × a_i 最大，f_min(i-1) × a_i 最小；
• 当前 a_i 是负数时：f_min(i-1) × a_i 反而最大，f_max(i-1) × a_i 反而最小。

所以两个来源都可能成为新的最大或最小值，必须同时考虑。

为什么要带一个 a_i？

如果前面累积的乘积都「帮倒忙」（比如 f_max(i-1) = 0），那么从 a_i 重新开始更优。

更新顺序注意：f_max 和 f_min 都由上一轮的 f_max、f_min 决定。所以必须先用临时变量存下上一轮的值，再计算本轮。

代码

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):
            a = nums[i]
            f_max[i] = max(f_max[i - 1] * a, f_min[i - 1] * a, a)
            f_min[i] = min(f_max[i - 1] * a, f_min[i - 1] * a, a)

        return max(f_max)

复杂度分析

• 时间复杂度：$O(n)$，遍历一次数组。
• 空间复杂度：$O(n)$，两个长度为 $n$ 的数组。

方法二：滚动变量（$O(1)$ 空间）

思路及解法

f_max(i) 和 f_min(i) 只和上一轮有关，可以用两个变量滚动维护，把空间压到 $O(1)$。

关键细节：更新 f_max 时，会用到上一轮的 f_min 和 f_max。如果先更新 f_max，再更新 f_min，f_min 计算时就会用到已经更新的 f_max，导致错误。

因此需要先用临时变量 mx、mn 保存上一轮的 f_max 和 f_min：

mx, mn = f_max, f_min
f_max = max(mx * a, mn * a, a)
f_min = min(mx * a, mn * a, a)

代码

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        f_max = f_min = ans = nums[0]

        for a in nums[1:]:
            mx, mn = f_max, f_min           # 先保存上一轮的值
            f_max = max(mx * a, mn * a, a)
            f_min = min(mx * a, mn * a, a)
            ans = max(ans, f_max)

        return ans

复杂度分析

• 时间复杂度：$O(n)$，遍历一次数组。
• 空间复杂度：$O(1)$，只用常数个变量。

两种方法对比

方法	时间	空间	特点
数组版	$O(n)$	$O(n)$	状态清晰，方便调试
滚动变量	$O(n)$	$O(1)$	空间最优，面试推荐

推荐：面试时直接写滚动变量版本，同时说明「需要先用临时变量保存上一轮的值，避免覆盖」。

与 LC 53 最大子数组和的对比

	LC 53 最大子数组和	LC 152 乘积最大子数组
转移	dp(i) = max(dp(i-1) + a_i, a_i)	f_max(i) = max(f_max(i-1)·a_i, f_min(i-1)·a_i, a_i)
只需要最大值吗	是	否，还需最小值
原因	加法不会翻转符号	负数 × 负数 = 正数，需要保留「很小的负数」

总结

• 核心观察：乘法里负数会翻转符号，只维护最大值不够，必须同时维护最小值；
• 转移方程：
  • f_max(i) = max(f_max(i-1)·a, f_min(i-1)·a, a)；
  • f_min(i) = min(f_max(i-1)·a, f_min(i-1)·a, a)；
• 边界：f_max(0) = f_min(0) = nums[0]；
• 滚动优化：用两个变量滚动更新，空间降到 $O(1)$；
• 易错点：更新 f_max 和 f_min 时要先用临时变量保存上一轮的值，否则会互相污染。

相关题目

• LC 53. 最大子数组和（加法版本，只需维护最大值）
• LC 1567. 乘积为正数的最长子数组长度（同样是正负符号的套路）