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

LeetCode 152题保姆级图解：用动态规划搞定乘积最大子数组（附C++/Java代码）

news 2026/5/11 22:18:20

LeetCode 152题动态规划实战：乘积最大子数组的视觉化解析与多语言实现

在算法学习的道路上，动态规划(DP)常常是让初学者望而生畏的难点之一。特别是当遇到像LeetCode 152题"乘积最大子数组"这样的问题时，传统的文字解释往往难以直观传达状态转移的精髓。本文将采用视觉化教学法，通过绘制状态转移图和数组变化过程，带你一步步理解为什么需要同时维护最大值和最小值两个DP数组。无论你是C++还是Java开发者，都能在这里找到清晰的实现路径。

1. 问题本质与核心挑战

给定一个整数数组nums，我们需要找到乘积最大的连续子数组。这里的"连续子数组"指的是数组中相邻元素组成的序列。与求和问题不同，乘积运算具有几个独特性质：

符号效应：负数会改变结果的符号，两个负数相乘得到正数
零值陷阱：任何数与零相乘都会归零
累积特性：绝对值的累积可能导致数值溢出或下溢

考虑示例数组[2,3,-2,4]，最大乘积子数组是[2,3]，结果为6。如果简单套用最大子数组和的思路，很可能会得到错误答案。这就是为什么我们需要更精细的动态规划策略。

关键观察：当前的最大乘积可能来自前一个最大值乘以正数，或者前一个最小值乘以负数，或者从当前元素重新开始。

2. 动态规划的双状态设计

2.1 状态定义可视化

我们需要同时跟踪两个状态：

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

数组: [2, 3, -2, 4] 索引: 0 1 2 3 max_dp演变: i=0: 2 (初始) i=1: max(3, 2*3) = 6 i=2: max(-2, 6*-2, -6*-2) = 12 i=3: max(4, 12*4, -2*4) = 48 min_dp演变: i=0: 2 (初始) i=1: min(3, 2*3) = 3 i=2: min(-2, 6*-2, 3*-2) = -12 i=3: min(4, -12*4, 12*4) = -48

2.2 状态转移方程图解

状态转移的核心逻辑可以用以下决策树表示：

当前元素nums[i] ├── 正数 → │ ├── max_dp[i] = max(nums[i], max_dp[i-1]*nums[i]) │ └── min_dp[i] = min(nums[i], min_dp[i-1]*nums[i]) └── 负数 → ├── max_dp[i] = max(nums[i], min_dp[i-1]*nums[i]) └── min_dp[i] = min(nums[i], max_dp[i-1]*nums[i])

3. 代码实现与语言特性对比

3.1 C++实现要点

class Solution { public: 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; } };

C++特性注意：

使用vector容器存储数组
max和min函数需要比较两个参数，嵌套使用处理三个参数的情况
空间优化：只维护前一个状态，无需存储整个DP数组

3.2 Java实现要点

class Solution { public int maxProduct(int[] nums) { int n = nums.length; if(n == 0) return 0; int maxProd = nums[0]; int minProd = nums[0]; int result = nums[0]; for(int i = 1; i < n; i++) { int curr = nums[i]; // Java的Math.max/min只能比较两个值 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; } }

Java特性注意：

数组使用int[]声明
Math.max()和Math.min()方法与C++略有不同
同样采用空间优化策略

4. 常见误区与调试技巧

4.1 典型错误模式

错误类型	错误表现	修正方法
单状态DP	只维护最大值，遇到负数序列失效	增加最小值状态跟踪
初始化不当	未正确处理第一个元素	初始化max/min为nums[0]
更新顺序错误	先更新max_dp导致min_dp计算错误	使用临时变量保存旧值

4.2 调试检查表

边界检查：
- 空数组输入
- 单元素数组
- 全正/全负数组
关键点验证：
- 遇到0时状态是否正确重置
- 负数是否触发最大值和最小值的交换
- 结果是否持续更新

可视化调试：

# 简单打印调试示例 def maxProduct(nums): max_dp, min_dp, res = nums[0], nums[0], nums[0] for i in range(1, len(nums)): print(f"i={i}, num={nums[i]}, before - max:{max_dp}, min:{min_dp}") temp_max = max(nums[i], max_dp*nums[i], min_dp*nums[i]) min_dp = min(nums[i], max_dp*nums[i], min_dp*nums[i]) max_dp = temp_max res = max(res, max_dp) print(f"after - max:{max_dp}, min:{min_dp}, res:{res}") return res