最大乘积子数组为什么要同时维护最大值和最小值？

简化版

最大乘积子数组需要同时维护以当前位置结尾的最大乘积 maxEnd 和最小乘积 minEnd。因为遇到负数时，之前的最小乘积乘上负数可能变成最大值；遇到 0 时状态会自然重置。

详细版

普通最大子数组和只需要维护一个“以当前位置结尾的最大和”，但乘积有符号翻转问题。设当前数为 x，以当前位置结尾的最大乘积可能来自 x、maxEnd * x 或 minEnd * x；最小乘积同理也要取这三者的最小值。

每一步更新全局答案 ans = max(ans, maxEnd)。初始值取第一个元素，遍历从第二个元素开始。时间复杂度 O(n)，空间复杂度 O(1)。

完整版教学

一、为什么最大和的套路不够用

最大子数组和中，如果前缀和为负，继续带着它只会拖累后面。但乘积不一样，负数乘负数会变成正数。

nums = [2, 3, -2, 4]
最大乘积是 2 * 3 = 6

nums = [-2, 3, -4]
最大乘积是 -2 * 3 * -4 = 24

第二个例子里，前面的负乘积不能随便丢，因为它可能被后面的负数翻成最大正数。

二、状态必须成对维护

定义：

maxEnd：以当前位置结尾的最大乘积
minEnd：以当前位置结尾的最小乘积

当前数 x 到来时，有三种选择：

来源	含义
`x`	从当前位置重新开始
`maxEnd * x`	接在之前最大乘积后面
`minEnd * x`	接在之前最小乘积后面

新的最大值取三者最大，新的最小值取三者最小。

记忆钩子：乘积 DP 里“最坏的负数”可能在下一个负数面前变成最好。

三、转移公式

设旧状态为 oldMax、oldMin，当前数为 x：

newMax = max(x, oldMax * x, oldMin * x)
newMin = min(x, oldMax * x, oldMin * x)
ans = max(ans, newMax)

注意必须用旧的 maxEnd 和 minEnd 同时计算，不能先更新 maxEnd 后再拿新值算 minEnd。

四、0 如何处理

0 会把任何乘积截断。公式里把 x 本身作为候选，已经自然处理了 0。

nums = [-2, 0, -1]
到 0 时：newMax = 0, newMin = 0
到 -1 时：可从 -1 重新开始
最大答案仍是 0

所以不一定要手写“遇到 0 重置”，统一公式更安全。

五、代码模板

int maxProduct(int[] nums) {
    int maxEnd = nums[0];
    int minEnd = nums[0];
    int ans = nums[0];

    for (int i = 1; i < nums.length; i++) {
        int x = nums[i];
        int oldMax = maxEnd;
        int oldMin = minEnd;

        maxEnd = Math.max(x, Math.max(oldMax * x, oldMin * x));
        minEnd = Math.min(x, Math.min(oldMax * x, oldMin * x));
        ans = Math.max(ans, maxEnd);
    }
    return ans;
}

如果使用语言存在整数溢出风险，要根据题目范围决定是否使用更大的数值类型。

六、用样例走一遍

以 [-2, 3, -4] 为例：

x	maxEnd	minEnd	ans
-2	-2	-2	-2
3	3	-6	3
-4	24	-12	24

关键就在最后一步：oldMin * -4 = 24 成为最大乘积。

七、常见误区与追问

误区：只维护最大乘积。 遇到负数时，最小乘积可能翻转成最大乘积。
误区：更新 minEnd 时使用已经更新后的 maxEnd。 两个新状态都必须来自旧状态。
误区：遇到 0 后直接跳过。 0 本身可能是最大答案，尤其数组全为负且被 0 分隔时。
追问：为什么不是滑动窗口？ 负数和 0 会破坏单调性，窗口扩张收缩没有稳定规则。
追问：复杂度是多少？ 单次遍历，时间 O(n)，空间 O(1)。
追问：和最大子数组和有什么区别？ 和只需要最大前缀状态，乘积需要最大和最小两个状态。

八、加强记忆

最大乘积子数组的核心是“负负得正”。普通线性 DP 只保留最大状态会丢掉未来翻盘的负数，所以必须同时保留 maxEnd 和 minEnd。每次面对当前数，都比较“重新开始、接最大、接最小”三种选择；0 不用特殊恐惧，公式会把它当作重新开始点。面试时用 [-2,3,-4] 解释最小值翻成最大值，基本就能讲清楚这题。

简化版

详细版