二刷 LeetCode：152. 乘积最大子数组 416. 分割等和子集 复盘笔记

目录

一、152. 乘积最大子数组

题目回顾

思路复盘

核心思路：同时维护最大值和最小值

易错点 & 二刷心得

二、416. 分割等和子集

题目回顾

思路复盘

核心思路：0-1 背包 DP

易错点 & 二刷心得

三、两道题的共性总结 & 二刷收获

---

这两道题是动态规划的经典考点，分别代表了带特殊状态的一维 DP和0-1 背包 DP，也是面试高频题型。二刷时我们重点拆解思路、优化写法，顺便把易错点和通用模板总结清楚。

---

一、152. 乘积最大子数组

题目回顾

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

思路复盘

这道题和「最大子数组和」很像，但因为负数和 0 的存在，直接用单变量 DP 会翻车：负数乘以负数会变成正数，之前的最小值可能变成最大值。

核心思路：同时维护最大值和最小值

1. 状态定义：
   • maxDp[i]：以nums[i]结尾的子数组的最大乘积
   • minDp[i]：以nums[i]结尾的子数组的最小乘积（因为负负得正，最小值可能变成最大值）
2. 状态转移：
   • 对于每个nums[i]，有三种选择：
     1. 只取当前元素nums[i]
     2. 用之前的最大值乘当前元素：maxDp[i-1] * nums[i]
     3. 用之前的最小值乘当前元素：minDp[i-1] * nums[i]
   • 状态转移方程：

     plaintext

     maxDp[i] = max(nums[i], maxDp[i-1] * nums[i], minDp[i-1] * nums[i]) minDp[i] = min(nums[i], maxDp[i-1] * nums[i], minDp[i-1] * nums[i])

3. 初始状态：maxDp[0] = minDp[0] = nums[0]
4. 结果：遍历过程中记录的最大值

Java 代码实现（优化空间版）

java

运行

public int maxProduct(int[] nums) { if (nums == null || nums.length == 0) return 0; int max = nums[0], min = nums[0], result = nums[0]; for (int i = 1; i < nums.length; i++) { // 保存之前的max，避免被覆盖 int prevMax = max; int prevMin = min; max = Math.max(nums[i], Math.max(prevMax * nums[i], prevMin * nums[i])); min = Math.min(nums[i], Math.min(prevMax * nums[i], prevMin * nums[i])); result = Math.max(result, max); } return result; }

易错点 & 二刷心得

1. 为什么要同时维护最小值？比如nums = [-2, 3, -4]，第一次计算到 3 时，最小值是 - 6，第二次乘以 - 4，得到 24，这就是最大值。
2. 空间优化技巧：不需要完整的dp数组，只需要用两个变量保存上一次的最大值和最小值即可，空间复杂度从 O (n) 降到 O (1)。
3. 0 的处理：当遇到 0 时，max 和 min 都会被重置为 0，后续计算会重新开始，不影响结果。

---

二、416. 分割等和子集

题目回顾

给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

思路复盘

这是0-1 背包问题的经典变形，核心是转化问题：

1. 先计算数组的总和sum，如果sum是奇数，直接返回false（无法分成两个相等的整数和）
2. 问题转化为：是否能从数组中选出一些数，使它们的和等于sum/2（目标容量）

核心思路：0-1 背包 DP

1. 状态定义：dp[j]表示是否能从数组中选出和为j的子集
2. 状态转移：
   • 对于每个数num，从后往前遍历背包容量j：
     • 如果j >= num，则dp[j] = dp[j] || dp[j - num]（不选 num 或选 num）
3. 初始状态：dp[0] = true（和为 0 的子集总是存在的，即不选任何数）
4. 结果：dp[target]，其中target = sum/2

Java 代码实现

java

运行

public boolean canPartition(int[] nums) { int sum = 0; for (int num : nums) { sum += num; } // 总和为奇数，无法分割 if (sum % 2 != 0) return false; int target = sum / 2; boolean[] dp = new boolean[target + 1]; dp[0] = true; for (int num : nums) { // 从后往前遍历，避免重复使用同一个元素 for (int j = target; j >= num; j--) { dp[j] = dp[j] || dp[j - num]; } } return dp[target]; }

易错点 & 二刷心得

1. 奇偶性判断：必须先判断总和是否为偶数，否则直接返回 false，这是很多人容易漏掉的边界条件。
2. 遍历顺序：必须从后往前遍历背包容量，否则会变成完全背包（可以重复使用元素），导致错误。
3. 空间优化：使用一维数组代替二维数组，空间复杂度从 O (n*target) 降到 O (target)，是 0-1 背包的标准优化方式。

---

三、两道题的共性总结 & 二刷收获

1. 动态规划的特殊状态处理：
   • 乘积最大子数组：因为负数的存在，必须同时维护最大值和最小值，避免状态丢失。
   • 分割等和子集：问题转化为 0-1 背包，体现了 DP 中 “问题转化” 的重要思路。
2. 优化意识：
   • 空间优化：从二维数组到一维数组，再到变量滚动更新，降低空间复杂度。
   • 边界优化：提前判断奇偶性、总和为 0 等情况，减少不必要的计算。
3. 面试重点：
   • 乘积最大子数组：重点是同时维护最大 / 最小值的逻辑，以及负数对状态的影响。
   • 分割等和子集：重点是问题转化为 0-1 背包，以及从后往前遍历的原因。