LC152　乘积最大子数组¶

中等通过率 44.6%python3核心代码模式动态规划样例通过牛客 AC数组动态规划

牛客原题　源码

讲解章节：线性 DP

一句话

负数会把最大变最小，所以必须同时维护以当前位置结尾的最大与最小乘积。

解题思路¶

这题考什么¶

与「最大子数组和」（见线性 DP）形状相同，但加法换成乘法之后，最优子结构被负号破坏了：加法里「前缀越大越好」永远成立，乘法里一个绝对值很大的负数乘上另一个负数会一跃成为最大值。只记最大值，遇到负数时就再也接不回来。

修补办法是把最小值也当成状态一起推：负的最小值是「潜在的最大值」，只等下一个负数把它翻正。

状态定义（两个状态，都以「必须以第 i 个元素结尾」为前提）：

hi[i] = 以 nums[i] 结尾的连续子数组的最大乘积
lo[i] = 以 nums[i] 结尾的连续子数组的最小乘积

转移方程：

hi[i] = max(nums[i], hi[i-1] * nums[i], lo[i-1] * nums[i])
lo[i] = min(nums[i], hi[i-1] * nums[i], lo[i-1] * nums[i])

三个候选分别是：从 nums[i] 另起一段、接在上一段的最大乘积后、接在最小乘积后。「另起一段」这一项不能省——上一段乘积为 0，或方向不利时，从头开始才是最优。答案是所有 hi[i] 里的最大值，不是 hi[n-1]，因为最优子数组不一定结尾在末位。

为什么「必须以 i 结尾」这个限定是必要的：只有钉死右端点，上一格的信息才能直接拼接。若状态定义成「前 i 个元素里的最优」，那一段可能早就断在中间，无法与 nums[i] 相乘。

本文件把三选一简化成两选一：当 nums[i] < 0 时先把 hi 与 lo 交换，再照常取 max(hi * x, x) 与 min(lo * x, x)。因为乘一个负数会把整条数轴翻转，交换恰好等价于在两个旧状态之间挑对了那一个。x = 0 时两式都得 0，交换与否都不影响，所以只需判 x < 0。

数据规模与复杂度¶

1 <= nums.length <= 2e4，-10 <= nums[i] <= 10，题面保证任何子数组的乘积都是 32 位整数。时间 O(n)，一趟扫描 2e4 步；空间 O(1)，三个标量。暴力枚举左右端点是 n 的平方 / 2 = 2e8 次乘法，Python 下没有指望。

值域只有 -10..10 看着很小，但连乘增长极快：连续 10 个 10 就已经是 1e10。题面的「保证是 32 位整数」是对数据的承诺而非对代码的要求—— Python 整数任意精度，即便数据越界也只会变慢不会溢出，这条约束在 C++ 里才需要认真对待。

坑在哪¶

只维护最大值必错。nums = [-2, 3, -4] 的答案是 24： -2 与 3 相乘得到的 -6 是当时的最小值，被最后的 -4 一乘才翻成最大。丢掉 lo 就只会得到 3。
交换必须发生在两条转移式之前。改成「先按旧的 hi、lo 算完再交换」，等于每次都用错的那一侧去乘：同样的 nums = [-2, 3, -4]，第三步会算出 hi = max(3 * -4, -4) = -4，答案退化成 3。
判断条件是 x < 0 而不是 x <= 0。x = 0 时两式结果都是 0，多做一次交换无害，但写成 x <= 0 会让读者误以为 0 也需要翻转，属于误导。
三个变量都从 nums[0] 起手，不能从 0 或 1 起手。从 1 起手会凭空多乘一个空前缀；从 0 起手则任何全负数组都会返回 0，而题目要求子数组非空。
best 要在循环里每步更新，不能只看最后一格。nums = [2, 3, -2, 4] 的答案 6 出现在第 2 个元素处，末位的 hi 只有 4。
lo 也要照常更新，哪怕它当下毫无用处——它是留给未来的负数用的。写成「只在 x < 0 时才更新 lo」会让 lo 停留在过期的值上。

样例复核¶

nums = [2, 3, -2, 4]，起手 hi = lo = best = 2。

x=3  : 非负，hi = max(6, 3) = 6, lo = min(6, 3) = 3, best = 6
x=-2 : 交换成 hi=3, lo=6；hi = max(-6, -2) = -2, lo = min(-12, -2) = -12
x=4  : 非负，hi = max(-8, 4) = 4, lo = min(-48, 4) = -48, best 仍为 6

返回 6，对应子数组 [2, 3]，与期望输出一致。

参考实现¶

solutions/leetcode/LC152/sol.py
from typing import List, Optional


class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # 滚动掉「下标」这一维：hi = 以当前元素结尾的最大乘积，lo = 最小乘积。
        # lo 必须一起维护——负的最小值是潜在的最大值，只等下一个负数把它翻正。
        # 三者都从 nums[0] 起手：题目要求子数组非空，从 0 或 1 起手都会引入空前缀
        hi = lo = best = nums[0]
        for x in nums[1:]:
            if x < 0:
                # 乘负数会把整条数轴翻转，原来的最小值才是新的最大值来源。
                # 交换必须在两条转移式之前做，否则等于用错的那一侧去乘
                hi, lo = lo, hi
            # 两个候选：接着前面那一段，或从 x 另起一段。
            # 「另起」这一项不能省——前一段乘积为 0 或方向不利时，重新起头才最优
            hi = max(hi * x, x)
            # lo 每步都要更新，哪怕当下用不上；它是留给后面的负数翻盘用的
            lo = min(lo * x, x)
            if hi > best:
                # 最优子数组不一定结尾在末位，所以答案要边扫边收，不能只看最后一格
                best = hi
        return best

LC152 乘积最大子数组¶