乘积最大子数组

可视化:双轨能量反转

nums=[-2,3,-4]，求乘积最大子数组。

先从反例理解为什么需要 curMin——再学三候选人竞争更新 curMax/curMin，用 ans 记录全局最优。

时间 O(n)空间 O(1)核心：curMax/curMin/ans · O(n)

题目1 / 9

三候选人竞争 · 双轨乘积 DP

Scene 1 · 题意：连续子数组的最大乘积

ans · 全局最大

-2

先理解题意，不急着写 DP

curMax · 以 i 结尾最大

curMin · 以 i 结尾最小

-2

-4

max 段 —min 段 —

状态面板

-2

prevMax

—

prevMin

—

curMax · 以 i 结尾最大-2

curMin · 以 i 结尾最小-2

ans · 全局最大-2

参考轨迹 · nums = [2, 3, -2, 4]（切换「完整轨迹」案例查看逐步高亮） · 4 步

i	x	prevMax	prevMin	candidates	curMax	curMin	ans
0	2	—	—	—	2	2	2
1	3	2	2	{3, 6, 6}	6	3	6
2	-2	6	3	{-2, -12, -6}	-2	-12	6
3	4	-2	-12	{4, -8, -48}	4	-48	6

CodeTrace · Go · 双轨 max/min

1func maxProduct(nums []int) int {
2    curMax := nums[0]
3    curMin := nums[0]
4    ans := nums[0]
5
6    for i := 1; i < len(nums); i++ {
7        x := nums[i]
8        prevMax, prevMin := curMax, curMin
9        curMax = max3(x, prevMax*x, prevMin*x)
10        curMin = min3(x, prevMax*x, prevMin*x)
11        if curMax > ans {
12            ans = curMax
13        }
14    }
15
16    return ans
17}

本步讲解 · Scene 1 · 题意：连续子数组的最大乘积

当前发生了什么

乘积 DP 和求和 DP 的心智模型不同。

为什么正确

LC53 只维护一个滚动和；LC152 需要双轨。

面试怎么说

这题和最大子数组和不同，乘积遇到负数会发生符号翻转，所以当前位置的最大乘积可能来自之前的最小乘积。遍历时维护以 i 结尾的最大乘积 curMax 和最小乘积 curMin，每一步从 x、prevMax×x、prevMin×x 三者中更新，再用 curMax 更新全局答案 ans。时间 O(n)，空间 O(1)。

人类输入

nums=[-2,3,-4]，求乘积最大子数组。

机制

每步从 x、prevMax×x、prevMin×x 三候选更新 curMax/curMin，再用 curMax 刷新全局 ans。

机器状态

curMax（以 i 结尾最大）、curMin（以 i 结尾最小）、ans（全局最大乘积）。

可观察结果

反例引入：最大乘积 24。

不变量

· curMax/curMin 是以 i 结尾的局部状态；ans 是全局答案，只增不减。
· 必须先保存 prevMax/prevMin，再更新 curMax/curMin，顺序不能乱。

常见误区

· 只维护 curMax：负×负时 prevMin×x 可反杀成最大，会漏掉最优解（如 [-2,3,-4] 漏 24）。
· 忘记 curMin：无法记录历史最小乘积，负数翻转时 curMax 来源丢失。
· 把 curMax 当成全局答案：curMax 每步重算，必须用 ans = max(ans, curMax) 记录全局最优。
· 没处理 0：0 切断乘积链，三候选皆 0，必须从当前格重启（如 [-2,0,-1] 答案是 0）。
· 更新顺序错误：先算 curMax 再算 curMin 会污染 prevMax，必须 oldMax, oldMin := curMax, curMin 先保存。

迁移练习

· LC53 最大和
· LC713 乘积小于 K

面试怎么说