当前位置：首页 > news >正文

LeetCode 152题别再用暴力了！一个动画看懂动态规划如何搞定乘积最大子数组

news 2026/5/13 2:20:14

动态规划解乘积最大子数组：从思维误区到可视化理解

很多人在解决LeetCode 152题"乘积最大子数组"时，会陷入一个常见的思维陷阱——仅维护最大值状态。这种看似合理的简化思路，在面对负数时会导致计算结果完全错误。让我们通过一个实际例子来揭示这个陷阱：

nums = [2, 3, -2, 4]

如果只记录最大值，当遇到第一个-2时，我们会得到：

前一步最大值：6 (2×3)
当前值：-2
新"最大值"：max(-2, 6×-2) = -2

这显然忽略了-12这个乘积实际上可能成为后续计算的关键（如果下一个数是负数，-12×负数会变成更大的正数）。

1. 为什么需要同时维护最大和最小值？

动态规划的核心在于状态定义。对于乘积问题，我们需要同时跟踪两个状态：

max_dp[i]：以nums[i]结尾的子数组的最大乘积
min_dp[i]：以nums[i]结尾的子数组的最小乘积

这种双状态设计源于乘法的一个独特性质：负负得正。具体来说：

当nums[i]为正数时：
- 最大乘积 = max(nums[i], 前一个最大乘积 × nums[i])
- 最小乘积 = min(nums[i], 前一个最小乘积 × nums[i])
当nums[i]为负数时：
- 最大乘积 = max(nums[i], 前一个最小乘积 × nums[i])
- 最小乘积 = min(nums[i], 前一个最大乘积 × nums[i])

关键提示：最小值状态看似多余，实则是为后续可能出现的负数做准备，确保不会错过"负负得正"的机会。

2. 状态转移的可视化过程

让我们用表格形式展示示例数组[2, 3, -2, 4]的完整计算过程：

数字	当前值	前max	前min	新max计算	新min计算	最终max	最终min	全局max
2	2	-	-	max(2, N/A)	min(2, N/A)	2	2	2
3	3	2	2	max(3, 2×3)	min(3, 2×3)	6	3	6
-2	-2	6	3	max(-2, 6×-2, 3×-2)	min(-2, 6×-2, 3×-2)	-2	-12	6
4	4	-2	-12	max(4, -2×4, -12×4)	min(4, -2×4, -12×4)	4	-48	6

从表格中可以清晰看到：

处理数字3时，常规思路有效
处理-2时，最小值-12被记录下来
虽然最后一步没有用到-12，但如果数组继续有负数，这个最小值就可能变成最大值

3. 代码实现的关键细节

基于上述分析，我们来看C++和Java的实现要点：

C++实现

int maxProduct(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; int max_prod = nums[0]; int min_prod = nums[0]; int result = nums[0]; for (int i = 1; i < n; i++) { int curr = nums[i]; // 需要临时变量，因为max_prod会被修改 int temp_max = max(curr, max(max_prod * curr, min_prod * curr)); min_prod = min(curr, min(max_prod * curr, min_prod * curr)); max_prod = temp_max; result = max(result, max_prod); } return result; }

Java实现

public int maxProduct(int[] nums) { if (nums.length == 0) return 0; int maxProd = nums[0]; int minProd = nums[0]; int result = nums[0]; for (int i = 1; i < nums.length; i++) { int curr = nums[i]; int tempMax = Math.max(curr, Math.max(maxProd * curr, minProd * curr)); minProd = Math.min(curr, Math.min(maxProd * curr, minProd * curr)); maxProd = tempMax; result = Math.max(result, maxProd); } return result; }

实现中的几个关键点：

使用临时变量保存新的max_prod，因为原始值在计算min_prod时还需要使用
每次迭代都更新全局最大值result
边界情况处理（空数组）

4. 算法优化与空间复杂度

观察状态转移方程可以发现，当前状态只依赖于前一个状态，因此我们可以将空间复杂度从O(n)优化到O(1)：

def maxProduct(nums): if not nums: return 0 max_prod = min_prod = result = nums[0] for num in nums[1:]: # 同时计算，避免使用临时变量 candidates = (num, max_prod * num, min_prod * num) max_prod, min_prod = max(candidates), min(candidates) result = max(result, max_prod) return result

这种优化在面试中尤为重要，它展示了我们对动态规划状态压缩的理解。时间复杂度保持O(n)，因为只需要一次遍历。