好的，我们来看 LeetCode 第 152 题「乘积最大子数组」。

1. 题目描述

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

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

示例 1：

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

示例 2：

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是连续子数组，并且乘积 2 也不是由连续子数组得到的。
而且乘积最大连续子数组是 [0]，乘积为 0。

2. 问题分析与初步思路

这个问题和「最大子数组和」（第 53 题）很像，但有一个关键区别：
乘法中，负负得正。
因此，不能只维护一个“当前最大值”，因为当前可能很小的负数，遇到下一个负数会变成很大的正数。

例子：nums = [2, 3, -2, -4]

• 到第 3 个数 -2 时，最大乘积是 6，最小乘积是 -12。
• 到第 4 个数 -4 时：
  • 用最大乘积 6 乘 -4 得 -24
  • 用最小乘积 -12 乘 -4 得 48（新的最大乘积）

所以我们需要同时记录当前的最大乘积和最小乘积。

3. 动态规划思路

定义两个变量：

• maxProd：以当前元素结尾的连续子数组的最大乘积
• minProd：以当前元素结尾的连续子数组的最小乘积

每一步更新：

• 如果当前数字是正数，乘上 maxProd 会更大，乘上 minProd 会更小。
• 如果当前数字是负数，乘上 maxProd 会变小，乘上 minProd 会变大（负负得正）。
• 还要考虑子数组从当前数字重新开始的情况（比如之前乘积是 0 或遇到 0 后）。

所以更新公式为：

tempMax = max(nums[i], maxProd * nums[i], minProd * nums[i])
tempMin = min(nums[i], maxProd * nums[i], minProd * nums[i])
maxProd = tempMax
minProd = tempMin

再用一个变量 globalMax 记录遍历过程中的最大值。

4. 逐步推导示例

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

初始：
maxProd = 2, minProd = 2, globalMax = 2

i=1 (nums[1]=3)：

• tempMax = max(3, 2*3=6, 2*3=6) = 6
• tempMin = min(3, 2*3=6, 2*3=6) = 3
• 更新：maxProd=6, minProd=3, globalMax=max(2,6)=6

i=2 (nums[2]=-2)：

• tempMax = max(-2, 6*(-2)=-12, 3*(-2)=-6) = -2
• tempMin = min(-2, 6*(-2)=-12, 3*(-2)=-6) = -12
• 更新：maxProd=-2, minProd=-12, globalMax=max(6,-2)=6

i=3 (nums[3]=-4)：

• tempMax = max(-4, (-2)*(-4)=8, (-12)*(-4)=48) = 48
• tempMin = min(-4, (-2)*(-4)=8, (-12)*(-4)=48) = -4
• 更新：maxProd=48, minProd=-4, globalMax=max(6,48)=48

最终结果：48

5. 处理 0 的情况

如果遇到 0，比如 nums = [-2, 0, -1]：

• 到 0 时，maxProd 和 minProd 都会变成 0。
• 然后从下一个数字重新开始计算。
• 这样能保证 globalMax 至少是 0（如果数组中有 0 且其他乘积都小于 0）。

推导 nums = [-2, 0, -1]：
初始：maxProd=-2, minProd=-2, globalMax=-2
i=1 (0)：

• tempMax = max(0, -2*0=0, -2*0=0) = 0
• tempMin = min(0, 0, 0) = 0
• 更新：maxProd=0, minProd=0, globalMax=max(-2,0)=0
  i=2 (-1)：
• tempMax = max(-1, 0*(-1)=0, 0*(-1)=0) = 0
• tempMin = min(-1, 0, 0) = -1
• 更新：maxProd=0, minProd=-1, globalMax=0

结果：0

6. 算法总结

1. 初始化 maxProd = minProd = globalMax = nums[0]
2. 从 i = 1 到 n-1 遍历：
   • tempMax = max(nums[i], maxProd * nums[i], minProd * nums[i])
   • tempMin = min(nums[i], maxProd * nums[i], minProd * nums[i])
   • maxProd = tempMax
   • minProd = tempMin
   • globalMax = max(globalMax, maxProd)
3. 返回 globalMax

时间复杂度：O(n)
空间复杂度：O(1)

7. 关键点回顾

• 乘法中负负得正，所以需要同时记录最大和最小乘积。
• 每个位置的最大/最小乘积可能来自三种情况：当前数本身、当前数乘以前一个位置的最大乘积、当前数乘以前一个位置的最小乘积。
• 遇到 0 时，最大最小乘积会重置为 0，然后重新开始。