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

目录一、152. 乘积最大子数组题目回顾思路复盘核心思路同时维护最大值和最小值易错点 二刷心得二、416. 分割等和子集题目回顾思路复盘核心思路0-1 背包 DP易错点 二刷心得三、两道题的共性总结 二刷收获这两道题是动态规划的经典考点分别代表了带特殊状态的一维 DP和0-1 背包 DP也是面试高频题型。二刷时我们重点拆解思路、优化写法顺便把易错点和通用模板总结清楚。一、152. 乘积最大子数组题目回顾给你一个整数数组nums请你找出数组中乘积最大的非空连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。思路复盘这道题和「最大子数组和」很像但因为负数和 0 的存在直接用单变量 DP 会翻车负数乘以负数会变成正数之前的最小值可能变成最大值。核心思路同时维护最大值和最小值状态定义maxDp[i]以nums[i]结尾的子数组的最大乘积minDp[i]以nums[i]结尾的子数组的最小乘积因为负负得正最小值可能变成最大值状态转移对于每个nums[i]有三种选择只取当前元素nums[i]用之前的最大值乘当前元素maxDp[i-1] * nums[i]用之前的最小值乘当前元素minDp[i-1] * nums[i]状态转移方程plaintextmaxDp[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])初始状态maxDp[0] minDp[0] nums[0]结果遍历过程中记录的最大值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; }易错点 二刷心得为什么要同时维护最小值比如nums [-2, 3, -4]第一次计算到 3 时最小值是 - 6第二次乘以 - 4得到 24这就是最大值。空间优化技巧不需要完整的dp数组只需要用两个变量保存上一次的最大值和最小值即可空间复杂度从 O (n) 降到 O (1)。0 的处理当遇到 0 时max 和 min 都会被重置为 0后续计算会重新开始不影响结果。二、416. 分割等和子集题目回顾给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。思路复盘这是0-1 背包问题的经典变形核心是转化问题先计算数组的总和sum如果sum是奇数直接返回false无法分成两个相等的整数和问题转化为是否能从数组中选出一些数使它们的和等于sum/2目标容量核心思路0-1 背包 DP状态定义dp[j]表示是否能从数组中选出和为j的子集状态转移对于每个数num从后往前遍历背包容量j如果j num则dp[j] dp[j] || dp[j - num]不选 num 或选 num初始状态dp[0] true和为 0 的子集总是存在的即不选任何数结果dp[target]其中target sum/2Java 代码实现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]; }易错点 二刷心得奇偶性判断必须先判断总和是否为偶数否则直接返回 false这是很多人容易漏掉的边界条件。遍历顺序必须从后往前遍历背包容量否则会变成完全背包可以重复使用元素导致错误。空间优化使用一维数组代替二维数组空间复杂度从 O (n*target) 降到 O (target)是 0-1 背包的标准优化方式。三、两道题的共性总结 二刷收获动态规划的特殊状态处理乘积最大子数组因为负数的存在必须同时维护最大值和最小值避免状态丢失。分割等和子集问题转化为 0-1 背包体现了 DP 中 “问题转化” 的重要思路。优化意识空间优化从二维数组到一维数组再到变量滚动更新降低空间复杂度。边界优化提前判断奇偶性、总和为 0 等情况减少不必要的计算。面试重点乘积最大子数组重点是同时维护最大 / 最小值的逻辑以及负数对状态的影响。分割等和子集重点是问题转化为 0-1 背包以及从后往前遍历的原因。