算法分析-乘积最大子数组

继续研究：乘积最大子数组

给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32 位整数。注意，一个只包含一个元素的数组的乘积是这个元素的值。

题目分析

这个题的关键在于处理 0 和负数，因为正数连乘只会越乘越大。

• 子串中有 0，乘积结果就是 0。

• 子串中有奇数个负数，越乘越小；有偶数个负数，负负得正，也会越来越大。

我尝试使用滑动窗口，但是发现窗口边界不好处理，因为负数遇到负数又直接反转了。隐约感觉需要用到动态规划，却无从下手。

思考一下午无果后直接看提示，果然需要用动态规划，但是这里的动态规划和前面打家劫舍一题里用到的思路完全不同。

动态规划

打家劫舍记的是"前 i 个的最优解"（前缀型）：dp[i] = 从第 0 个到第 i 个，最多能偷多少。答案就是最后一个状态，不用回头找。

乘积最大记的是"以 i 结尾的最优解"（结尾型）：cur[i] = 必须以 i 结尾的连续段的最大乘积。答案不在最后，得在过程中一路 max 收集。

打家劫舍可以"不偷第 i 家"，这个选项给了它一条逃生通道——dp[i-1] 直接继承过来，不需要知道第 i-1 家具体偷没偷。所以前缀最优能一路无脑往下传。

乘积最大没有这条通道。你要接上 nums[i]，就必须贴着 i-1，所以上一段子数组必须"以 i-1 结尾"。而"前 i-1 个的最优解"很可能不以 i-1 结尾，接不上。于是你只能记"以 i 结尾"，代价就是答案要中途收集。

只要题目要求"连续"（子数组、子串），DP 状态基本都得定义成"以 i 结尾"；不要求连续、能跳着选（打家劫舍、背包、最长递增子序列），才常见"前 i 个"的前缀口径。

一句话区分：连续问题松"起点"，不连续问题松"中间"。

回到这个题，核心在于：任意连续子数组，一定以某个下标 i 结尾。所以我只要对每个 i 都算出"以 i 结尾的最大乘积"，再全局取最大，就覆盖了所有情况，一个不漏。

那"以 i 结尾"的乘积有几种可能？只有两种：

1. 只含 nums[i] 自己（前面的全不要）
2. 接在"以 i-1 结尾"的某个子数组后面

关键是第 2 种。前面的子数组有无数个（可以从任意位置开头），但它们的乘积里，只有两个极端值得接：

• 最大的那个——nums[i] 是正数时，接它越乘越大

• 最小的那个——nums[i] 是负数时，接它负负得正

即每个位置的两个状态，能完全代表前面所有子数组的信息。

所以我们遍历到某一个数 n 的时候，记录下以当前这个位置结尾的最大乘积 cur_max 和最小乘积 cur_min。到下一个数的时候，就可以与这两个数相乘，然后把 cur_max、cur_min 更新成在它那个位置结尾的最大乘积，方便它的下家去计算。

则有

cur_max = max(n * last_max, n * last_min)
cur_min = min(n * last_max, n * last_min)

还要考虑一种情况，如果 n 是 0，那么一直乘下去，所有的乘积也都变成 0，即包含了 0 的子串乘积就是 0。

那么如何让子串不包含 0 呢？我们注意到 0 的后一项的数，如果还拿前面的 cur_max、cur_min 来与它相乘，那么到它的这一步保留的结果也都是 0，意味着它与前面的 0 形成了子串。

我们这时候如果不保留 0，而是从它重新开始，它自己组成子串，那么这一步的 cur_max、cur_min 就应该保留它自己，意味着它自己单干了。

所以更新 cur_max、cur_min 的方法上再加上它自己：

cur_max = max(n * last_max, n * last_min, n)
cur_min = min(n * last_max, n * last_min, n)

这里的 last_max、last_min 就是上一步的 cur_max、cur_min 。

最后，我们再将每一步得到的结果中最大的一个 cur_max 用一个变量来存储，直到遍历完整个数组，这个变量就是我们要找的乘积最大子数组的乘积。

def maxProduct(self, nums: list[int]) -> int:
    result = float("-inf") # 无穷小
    cur_max = cur_min = 1
    for n in nums:
        a, b, c = n, n * cur_max, n * cur_min
        cur_max, cur_min = max(a, b, c), min(a, b, c)
        result = max(result, cur_max)
    return result

cur_max、cur_min 初始化为 1，因为 1 是乘法的单位元，第一轮 n * 1 = n，正好落地。result 用 float("-inf") 起步，保证第一个元素一定把它顶掉。

时间 $O(n)$：一趟遍历，每轮都是常数次乘法和比较。

空间 $O(1)$：只维护 cur_max、cur_min、result 三个变量，不随 n 增长。