先坦白一句这道题我刷了三遍才算真正吃透。第一遍用暴力枚举在大数组上直接超时第二遍想偷懒套“最大子数组和”的转移方程结果被负数的符号变化狠狠上了一课第三遍才彻底理解动态规划里为什么要同时维护“最大”和“最小”两个状态。LeetCode 152这个题表面是求一个连续子数组的乘积最大值实际考的是你对乘法符号特性的理解深度以及能不能从“加法场景”平滑迁移到“乘法场景”。本文我用Java把常见的几种解法全部拆开揉碎讲一遍重点推导动态规划的状态定义和转移方程再附上踩坑记录。无论你是刚接触动态规划的新手还是准备面试想系统过一遍经典题型的同学这篇都值得收藏。1. 题目拆解乘积最大子数组到底在考什么1.1 先读懂题意连续、非空、乘积最大题目本身很短给定一个整数数组 nums找出一个连续子数组使得该子数组的乘积最大返回这个最大值。子数组要求连续并且至少包含一个元素。举个例子nums [2, 3, -2, 4]所有连续子数组里[2, 3]的乘积是6[4]的乘积是4[2, 3, -2]的乘积是-12所以最大值是6。注意这里答案不一定是整个数组的乘积因为负数的存在会让“越长”反而“越小”。再看一个例子nums [-2, 0, -1]最大乘积是0而不是2。因为包含0的任意子数组乘积都是0不包含0的只有[-2]或者[-1]乘积分别是-2和-1都不如0大。这个例子说明遇到0时乘积会“重置”不能抱着前面的负数不放手。题目还有个很容易忽略的点数组元素可以是正数、负数、0三种情况都要能处理。之前有人问我如果所有元素都是正数那最大乘积不就是整个数组的乘积吗确实如此但有负数存在后问题就变得有趣了一个负数是减分项两个负数却可能变成加分项这就是这道题和“最大子数组和”最本质的区别。1.2 暴力法为什么不可行O(n^2)的时间代价很多人第一反应就是枚举所有子数组用两个指针 i 和 j 圈定区间用一个临时变量累乘区间内所有元素边乘边更新答案。这种方法逻辑上没有任何问题代码也简单。public int maxProductBruteForce(int[] nums) { int max Integer.MIN_VALUE; for (int i 0; i nums.length; i) { int product 1; for (int j i; j nums.length; j) { product * nums[j]; max Math.max(max, product); } } return max; }但是当数组长度达到10万级别时双重循环要执行约5亿次乘法实际运行时间会到秒级以上在在线评测环境里几乎必挂。暴力法作为理解题意的辅助工具是合格的但绝不是最优解。也有人会问能不能用前缀积数组来加速比如 prefix[i] 表示从开头到第 i 个元素的乘积然后通过 prefix[j] / prefix[i-1] 计算区间乘积。这个思路在数组全是正数时非常完美可一旦出现0除法就会遇到分母为0的问题退一步说就算用特殊标记处理0负数区间的乘积符号和大小也不能靠简单的除法得到。所以前缀积在这里并不是一个干净的解法真正干净的解法还是要靠动态规划。2. 从“最大子数组和”到“乘积最大子数组”核心难点解析2.1 直接套用加法模型的陷阱很多人在做这道题之前都刷过LeetCode 53题“最大子数组和”。那道题的动态规划转移方程非常简洁dp[i] max(dp[i-1] nums[i], nums[i])含义是以第 i 个元素结尾的最大子数组和要么是“从前面延续过来”要么是“从当前元素重新开始”。因为加法没有正负符号反转的问题维护一个“最大和”就够了。我一开始也是这么想的把加法换成乘法dp[i] max(dp[i-1] * nums[i], nums[i])然后提交挂了。原因很快就找到了。比如数组 [-2, 3, -4]按上面这个状态转移i0dp -2答案 -2i1dp max(-2*3-6, 3) 3答案 3i2dp max(3*-4-12, -4) -4答案 3可实际最大乘积是多少是整个数组 (-2) * 3 * (-4) 24。为什么漏掉了因为在 i1 时我们放弃了“以 -2 结尾的子数组乘积 -6”觉得它太小了。可没想到 -6 和后面的 -4 相乘时负负得正直接变成 24。这就说明在乘法场景下一个“看起来很差的最小值”可能在关键时刻变成“最大值”的种子。加法里没有这种现象或者说加法中“负数种子”永远翻不了身但乘法里负数种子有逆袭的机会。2.2 为什么必须同时维护“最大”和“最小”核心原因就一句话乘以一个负数大小关系会反转。假设当前维护着一个状态值它可能是正数也可能是负数。当新的 nums[i] 是正数时最大值乘以它还是最大最小值乘以它还是最小方向不变但当 nums[i] 是负数时最大值乘以负数会变成最小的候选最小值乘以负数反而变成最大的候选。如果我们只盯着最大值就会把“最小值乘以负数”这个可能的超级选项直接忽略掉。所以状态定义必须升级成两个fMax[i]以 nums[i] 结尾的子数组的最大乘积fMin[i]以 nums[i] 结尾的子数组的最小乘积二者都要维护因为 fMin[i] 可能在未来某一步“翻身”。转移方程也要同时考虑三种来源fMax[i] max(fMax[i-1] * nums[i], fMin[i-1] * nums[i], nums[i])fMin[i] min(fMax[i-1] * nums[i], fMin[i-1] * nums[i], nums[i])这里为什么还要单独拿 nums[i] 出来比较因为子数组是连续的当前位置可以选择“不延续前面的任何子数组”而是以自己为起点重新开始。比如前面算出来的乘积是0或者当前元素比延续过来的乘积更大都应该从当前元素重新起头。2.3 用生活类比理解状态同步更新可以把 fMax 和 fMin 想象成两个口袋一个装“当前能拿到的最大乘积”一个装“当前能拿到的最小乘积”。数组每往前走一步相当于抽一张新牌然后要把这张牌分别和两个口袋里的值相乘再看看结果是大还是小。举个例子你手里两个口袋分别是 6 和 3抽到一张牌是 -2那么6 * (-2) -12这个数会变成最小口袋的有力竞争者3 * (-2) -6这个数反而会变成最大口袋的有力竞争者同时不要忘了还可以选择“扔掉之前所有牌只用 -2 重新开始”。这就是和 nums[i] 单独比较的含义。整个过程像拿着一根绳子最大值和最小值互相拉扯、彼此托底缺了哪一个另一个都会在某次遇到负数时彻底失效。我在实际推导中习惯把每一步的 fMax 和 fMin 都列成表格这样能直观看到它们如何交替变化比空想转移方程可靠得多。3. Java 多种解法实现从滚动变量到数组DP3.1 推荐解法双变量滚动更新这是面试中最推荐写出来的版本时间复杂度 O(n)空间复杂度 O(1)。只维护两个变量分别表示“以当前元素结尾的最大乘积”和“以当前元素结尾的最小乘积”每次迭代时使用旧值计算新值最后更新答案。public int maxProduct(int[] nums) { int max nums[0]; int min nums[0]; int ans nums[0]; for (int i 1; i nums.length; i) { int curMax Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]); int curMin Math.min(Math.min(max * nums[i], min * nums[i]), nums[i]); max curMax; min curMin; ans Math.max(ans, max); } return ans; }这里的核心操作是把当前的 max 和 min 先保存成局部变量或者直接用 curMax、curMin 把这些新值算出来再做赋值。一定不要先更新 max 再使用 max 去更新 min因为那样会污染计算。拿 nums [2, 3, -2, 4] 走一遍初始化 max2min2ans2。i1 时max36min36取和3比较得 curMax6curMin3i2 时max-2 这一轮前最大值是6min36*(-2)-123*(-2)-6和-2比较后 curMax-2curMin-12i3 时max-2min-12-24-8-124-48和4比较后 curMax4curMin-48。最终 ans 在 i1 时取到6返回6。3.2 便于理解的辅助数组DP版本有些朋友不太习惯滚动变量觉得两个变量之间的更新关系容易绕晕。那可以先写辅助数组版本思路完全一致只不过把状态存进数组方便打印和调试。public int maxProductWithArray(int[] nums) { int n nums.length; int[] dpMax new int[n]; int[] dpMin new int[n]; dpMax[0] nums[0]; dpMin[0] nums[0]; int ans nums[0]; for (int i 1; i n; i) { dpMax[i] Math.max(Math.max(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]), nums[i]); dpMin[i] Math.min(Math.min(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]), nums[i]); ans Math.max(ans, dpMax[i]); } return ans; }这个版本的空间复杂度是 O(n)面试时可以提一句“可以优化成 O(1)”然后顺手改成滚动变量版本观感会很好。从学习角度来说数组版更容易和状态定义一一对应dpMax[i] 对应 fMax[i]dpMin[i] 对应 fMin[i]调试时把数组打印出来每一步的变化一目了然。3.3 巧思版本负数时交换最大值与最小值再讲一种很有启发性的写法思路来自对“乘法反转大小关系”的观察如果当前元素是负数那么最大值乘完之后会变成最小值最小值乘完之后会变成最大值。所以可以先交换 max 和 min再统一做乘法和比较。public int maxProductWithSwap(int[] nums) { int max 1; int min 1; int ans Integer.MIN_VALUE; for (int num : nums) { if (num 0) { int tmp max; max min; min tmp; } max Math.max(max * num, num); min Math.min(min * num, num); ans Math.max(ans, max); } return ans; }注意这里初始化的技巧max 和 min 都初始化为1而不是 nums[0]因为我们要在循环里统一处理所有元素包括第一个元素。1乘以任何数都等于它自身相当于一个恒等变换。这个版本我第一次看到时觉得很妙它的本质和双变量版是完全等价的只是把“负数会让大小反转”这个逻辑显式写了出来。面试时如果能把“为什么负数时交换 max 和 min”解释清楚面试官通常会很满意。3.4 暴力法的复杂度分析与参照价值暴力法代码前面已经给过了时间复杂度 O(n^2)空间复杂度 O(1)。它的价值在于验证答案写完动态规划解法后可以用暴力法在随机小规模数组上对比结果确认转移方程没有写错。我平时验证状态转移方程时会写一个小的测试脚本生成随机数组同时跑暴力解法和动态规划解法比较结果是否一致。这一步能帮你在提交前把所有边界问题暴露出来。千万别嫌麻烦算法题里很多“我觉得没问题但提交就错”的情况都是因为某些隐蔽边界没有覆盖到。4. 边界条件与常见坑位这些细节决定成败4.1 数组长度为1时能否正确处理当 nums [-1] 时任何解法都应该返回 -1。滚动变量版本里初始化 maxminansnums[0]循环不执行直接返回 -1。如果初始化的值写错了比如把 ans 初始化成 0那么单元素数组 [-1] 就会错误地返回 0。这是最常见的初始化错误。4.2 初始化值选择为什么不能用0或Integer.MIN_VALUE有些同学习惯把 ans 初始化为 Integer.MIN_VALUE这在很多最大值类题目里是对的但在乘积题里要小心。假设把 max 或者 min 初始化为0而数组全是负数比如 [-1, -2]那么 max 一开始是0乘以 -1 还是0乘以 -2 还是0最后答案会错误地变成0而不是真正的2。因为0乘以任何数都是0这个“0”像一个污染源会把所有乘积清零。所以滚动变量版最安全的写法是max、min、ans 全部初始化为 nums[0]。这样既避免空数组问题也避免0污染问题。至于“先乘再比较”的交换写法由于它的设计就是在每一轮统一处理当前元素所以 max 和 min 初始化为1是安全的但 ans 必须初始化为 Integer.MIN_VALUE因为它要在循环里收集每一轮的结果。4.3 为什么必须单独维护全局答案 ans动态规划里fMax[i] 表示“以第 i 个元素结尾”的最大乘积但最终答案不一定是最后那个元素结尾的子数组。比如 [2, 3, -2, 4] 里最大乘积 6 是以第1个元素结尾的子数组 [2,3] 产生的而不是以最后一个元素结尾的。所以必须用一个额外的 ans在每一轮迭代中记录历史最大值。这一点和“最长递增子序列”之类的问题很像状态定义是“以 i 结尾”的但答案要扫描所有状态取最大值。如果直接用最后一个 fMax 作为答案遇到最大答案在中间出现的情况就会出错。4.4 滚动更新的先后顺序先算后赋避免污染如果在双变量版里这样写max Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]); min Math.min(Math.min(max * nums[i], min * nums[i]), nums[i]);第二行里的 max 已经是更新过的值了它是“以当前元素结尾的新 max”再拿它去和 min 相乘逻辑就乱了。正确做法是用 curMax 和 curMin 两个局部变量同时保存新值或者先把旧值备份出来。这个坑不亲自踩一次很难注意到因为它不报错只是答案偶尔不对。4.5 关于溢出的思考这道题在LeetCode的数据范围下int 是够用的。但实际面试中如果数组元素很大或者很长乘积可能超过 int 范围。可以提一句“如果数据范围更大把变量类型换成 long或者结合说明使用合适的数据结构”面试官通常会觉得你有工程意识。不过不要过度设计LeetCode 环境里用 int 是标准做法。5. 相似题型与进阶扩展刷一道顶五道5.1 和LeetCode 53题“最大子数组和”的对比把两道题放在一起看是最有效的学习方式。最大子数组和的转移方程只需要一个 dp 值因为加法中负数的符号效应不会反转大小关系。最大子数组乘积则必须维护两个值核心变量是“负负得正带来的大小反转”。对比表格对比项最大子数组和53题乘积最大子数组152题状态数量一个dp即可必须维护max和min两个状态转移方程max(prev cur, cur)max(max(prevMax*cur, prevMin*cur), cur)负数的处理负数只是变小不会反转趋势负数会反转最大值与最小值的角色能否用贪心可以本质上是滚动DP不行必须同时跟踪两个极值这个对比在面试中非常有用。面试官如果先让你写53题然后让你写152题你要能清晰说出“为什么53题的思路不能直接套过来”这比闷头写对代码更分。5.2 进阶变体返回最大乘积子数组本身有时候面试官会追问不只返回最大值还要返回这个子数组。思路是在滚动更新的同时记录边界下标。每当 ans 被更新时记录当前的结束下标同时维护当前最优片段的起始下标。因为负数翻转会让“最优起点”变得复杂通常记录区间的方法是在每次“从当前元素重新开始”时更新候选起点在每次 ans 被更新时固定答案区间。这个代码比纯返回值要长一些但核心逻辑完全一致有兴趣的读者可以自己实现一遍。5.3 其他变体思路还有一类变体是求“乘积最小的连续子数组”只需要把状态转移中 max 和 min 的角色对调其他完全不变。以及考虑环形数组时的最大乘积子数组问题通常做法是拆成两种情况不跨越边界的最大乘积以及跨越边界的情况通过求最小子数组乘积再用总乘积除以最小子数组乘积来得到跨越边界的最大乘积。当然这里要注意除以零的问题遇到0还得单独处理。这些变体没有必要全刷一遍但理解了152题的核心思想后遇到它们都能快速迁移。动态规划题就是这样代码量不大难的是状态定义和不同场景下的变化逻辑吃透一道经典题的价值远大于囫囵吞枣刷十道简单题。我个人在实际练习中的体会是这题第一次做错非常正常重点是要把错误对照着“负负得正”这个本质去复盘。找一个包含正数、负数、零的测试用例把每一步 fMax 和 fMin 都手算出来写一次表格以后再遇到同类题基本就不会慌了。如果面试时能主动讲出“为什么需要两个状态”和“负数如何导致大小反转”这题基本上就拿下了。
先坦白一句这道题我刷了三遍才算真正吃透。第一遍用暴力枚举在大数组上直接超时第二遍想偷懒套“最大子数组和”的转移方程结果被负数的符号变化狠狠上了一课第三遍才彻底理解动态规划里为什么要同时维护“最大”和“最小”两个状态。LeetCode 152这个题表面是求一个连续子数组的乘积最大值实际考的是你对乘法符号特性的理解深度以及能不能从“加法场景”平滑迁移到“乘法场景”。本文我用Java把常见的几种解法全部拆开揉碎讲一遍重点推导动态规划的状态定义和转移方程再附上踩坑记录。无论你是刚接触动态规划的新手还是准备面试想系统过一遍经典题型的同学这篇都值得收藏。1. 题目拆解乘积最大子数组到底在考什么1.1 先读懂题意连续、非空、乘积最大题目本身很短给定一个整数数组 nums找出一个连续子数组使得该子数组的乘积最大返回这个最大值。子数组要求连续并且至少包含一个元素。举个例子nums [2, 3, -2, 4]所有连续子数组里[2, 3]的乘积是6[4]的乘积是4[2, 3, -2]的乘积是-12所以最大值是6。注意这里答案不一定是整个数组的乘积因为负数的存在会让“越长”反而“越小”。再看一个例子nums [-2, 0, -1]最大乘积是0而不是2。因为包含0的任意子数组乘积都是0不包含0的只有[-2]或者[-1]乘积分别是-2和-1都不如0大。这个例子说明遇到0时乘积会“重置”不能抱着前面的负数不放手。题目还有个很容易忽略的点数组元素可以是正数、负数、0三种情况都要能处理。之前有人问我如果所有元素都是正数那最大乘积不就是整个数组的乘积吗确实如此但有负数存在后问题就变得有趣了一个负数是减分项两个负数却可能变成加分项这就是这道题和“最大子数组和”最本质的区别。1.2 暴力法为什么不可行O(n^2)的时间代价很多人第一反应就是枚举所有子数组用两个指针 i 和 j 圈定区间用一个临时变量累乘区间内所有元素边乘边更新答案。这种方法逻辑上没有任何问题代码也简单。public int maxProductBruteForce(int[] nums) { int max Integer.MIN_VALUE; for (int i 0; i nums.length; i) { int product 1; for (int j i; j nums.length; j) { product * nums[j]; max Math.max(max, product); } } return max; }但是当数组长度达到10万级别时双重循环要执行约5亿次乘法实际运行时间会到秒级以上在在线评测环境里几乎必挂。暴力法作为理解题意的辅助工具是合格的但绝不是最优解。也有人会问能不能用前缀积数组来加速比如 prefix[i] 表示从开头到第 i 个元素的乘积然后通过 prefix[j] / prefix[i-1] 计算区间乘积。这个思路在数组全是正数时非常完美可一旦出现0除法就会遇到分母为0的问题退一步说就算用特殊标记处理0负数区间的乘积符号和大小也不能靠简单的除法得到。所以前缀积在这里并不是一个干净的解法真正干净的解法还是要靠动态规划。2. 从“最大子数组和”到“乘积最大子数组”核心难点解析2.1 直接套用加法模型的陷阱很多人在做这道题之前都刷过LeetCode 53题“最大子数组和”。那道题的动态规划转移方程非常简洁dp[i] max(dp[i-1] nums[i], nums[i])含义是以第 i 个元素结尾的最大子数组和要么是“从前面延续过来”要么是“从当前元素重新开始”。因为加法没有正负符号反转的问题维护一个“最大和”就够了。我一开始也是这么想的把加法换成乘法dp[i] max(dp[i-1] * nums[i], nums[i])然后提交挂了。原因很快就找到了。比如数组 [-2, 3, -4]按上面这个状态转移i0dp -2答案 -2i1dp max(-2*3-6, 3) 3答案 3i2dp max(3*-4-12, -4) -4答案 3可实际最大乘积是多少是整个数组 (-2) * 3 * (-4) 24。为什么漏掉了因为在 i1 时我们放弃了“以 -2 结尾的子数组乘积 -6”觉得它太小了。可没想到 -6 和后面的 -4 相乘时负负得正直接变成 24。这就说明在乘法场景下一个“看起来很差的最小值”可能在关键时刻变成“最大值”的种子。加法里没有这种现象或者说加法中“负数种子”永远翻不了身但乘法里负数种子有逆袭的机会。2.2 为什么必须同时维护“最大”和“最小”核心原因就一句话乘以一个负数大小关系会反转。假设当前维护着一个状态值它可能是正数也可能是负数。当新的 nums[i] 是正数时最大值乘以它还是最大最小值乘以它还是最小方向不变但当 nums[i] 是负数时最大值乘以负数会变成最小的候选最小值乘以负数反而变成最大的候选。如果我们只盯着最大值就会把“最小值乘以负数”这个可能的超级选项直接忽略掉。所以状态定义必须升级成两个fMax[i]以 nums[i] 结尾的子数组的最大乘积fMin[i]以 nums[i] 结尾的子数组的最小乘积二者都要维护因为 fMin[i] 可能在未来某一步“翻身”。转移方程也要同时考虑三种来源fMax[i] max(fMax[i-1] * nums[i], fMin[i-1] * nums[i], nums[i])fMin[i] min(fMax[i-1] * nums[i], fMin[i-1] * nums[i], nums[i])这里为什么还要单独拿 nums[i] 出来比较因为子数组是连续的当前位置可以选择“不延续前面的任何子数组”而是以自己为起点重新开始。比如前面算出来的乘积是0或者当前元素比延续过来的乘积更大都应该从当前元素重新起头。2.3 用生活类比理解状态同步更新可以把 fMax 和 fMin 想象成两个口袋一个装“当前能拿到的最大乘积”一个装“当前能拿到的最小乘积”。数组每往前走一步相当于抽一张新牌然后要把这张牌分别和两个口袋里的值相乘再看看结果是大还是小。举个例子你手里两个口袋分别是 6 和 3抽到一张牌是 -2那么6 * (-2) -12这个数会变成最小口袋的有力竞争者3 * (-2) -6这个数反而会变成最大口袋的有力竞争者同时不要忘了还可以选择“扔掉之前所有牌只用 -2 重新开始”。这就是和 nums[i] 单独比较的含义。整个过程像拿着一根绳子最大值和最小值互相拉扯、彼此托底缺了哪一个另一个都会在某次遇到负数时彻底失效。我在实际推导中习惯把每一步的 fMax 和 fMin 都列成表格这样能直观看到它们如何交替变化比空想转移方程可靠得多。3. Java 多种解法实现从滚动变量到数组DP3.1 推荐解法双变量滚动更新这是面试中最推荐写出来的版本时间复杂度 O(n)空间复杂度 O(1)。只维护两个变量分别表示“以当前元素结尾的最大乘积”和“以当前元素结尾的最小乘积”每次迭代时使用旧值计算新值最后更新答案。public int maxProduct(int[] nums) { int max nums[0]; int min nums[0]; int ans nums[0]; for (int i 1; i nums.length; i) { int curMax Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]); int curMin Math.min(Math.min(max * nums[i], min * nums[i]), nums[i]); max curMax; min curMin; ans Math.max(ans, max); } return ans; }这里的核心操作是把当前的 max 和 min 先保存成局部变量或者直接用 curMax、curMin 把这些新值算出来再做赋值。一定不要先更新 max 再使用 max 去更新 min因为那样会污染计算。拿 nums [2, 3, -2, 4] 走一遍初始化 max2min2ans2。i1 时max36min36取和3比较得 curMax6curMin3i2 时max-2 这一轮前最大值是6min36*(-2)-123*(-2)-6和-2比较后 curMax-2curMin-12i3 时max-2min-12-24-8-124-48和4比较后 curMax4curMin-48。最终 ans 在 i1 时取到6返回6。3.2 便于理解的辅助数组DP版本有些朋友不太习惯滚动变量觉得两个变量之间的更新关系容易绕晕。那可以先写辅助数组版本思路完全一致只不过把状态存进数组方便打印和调试。public int maxProductWithArray(int[] nums) { int n nums.length; int[] dpMax new int[n]; int[] dpMin new int[n]; dpMax[0] nums[0]; dpMin[0] nums[0]; int ans nums[0]; for (int i 1; i n; i) { dpMax[i] Math.max(Math.max(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]), nums[i]); dpMin[i] Math.min(Math.min(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]), nums[i]); ans Math.max(ans, dpMax[i]); } return ans; }这个版本的空间复杂度是 O(n)面试时可以提一句“可以优化成 O(1)”然后顺手改成滚动变量版本观感会很好。从学习角度来说数组版更容易和状态定义一一对应dpMax[i] 对应 fMax[i]dpMin[i] 对应 fMin[i]调试时把数组打印出来每一步的变化一目了然。3.3 巧思版本负数时交换最大值与最小值再讲一种很有启发性的写法思路来自对“乘法反转大小关系”的观察如果当前元素是负数那么最大值乘完之后会变成最小值最小值乘完之后会变成最大值。所以可以先交换 max 和 min再统一做乘法和比较。public int maxProductWithSwap(int[] nums) { int max 1; int min 1; int ans Integer.MIN_VALUE; for (int num : nums) { if (num 0) { int tmp max; max min; min tmp; } max Math.max(max * num, num); min Math.min(min * num, num); ans Math.max(ans, max); } return ans; }注意这里初始化的技巧max 和 min 都初始化为1而不是 nums[0]因为我们要在循环里统一处理所有元素包括第一个元素。1乘以任何数都等于它自身相当于一个恒等变换。这个版本我第一次看到时觉得很妙它的本质和双变量版是完全等价的只是把“负数会让大小反转”这个逻辑显式写了出来。面试时如果能把“为什么负数时交换 max 和 min”解释清楚面试官通常会很满意。3.4 暴力法的复杂度分析与参照价值暴力法代码前面已经给过了时间复杂度 O(n^2)空间复杂度 O(1)。它的价值在于验证答案写完动态规划解法后可以用暴力法在随机小规模数组上对比结果确认转移方程没有写错。我平时验证状态转移方程时会写一个小的测试脚本生成随机数组同时跑暴力解法和动态规划解法比较结果是否一致。这一步能帮你在提交前把所有边界问题暴露出来。千万别嫌麻烦算法题里很多“我觉得没问题但提交就错”的情况都是因为某些隐蔽边界没有覆盖到。4. 边界条件与常见坑位这些细节决定成败4.1 数组长度为1时能否正确处理当 nums [-1] 时任何解法都应该返回 -1。滚动变量版本里初始化 maxminansnums[0]循环不执行直接返回 -1。如果初始化的值写错了比如把 ans 初始化成 0那么单元素数组 [-1] 就会错误地返回 0。这是最常见的初始化错误。4.2 初始化值选择为什么不能用0或Integer.MIN_VALUE有些同学习惯把 ans 初始化为 Integer.MIN_VALUE这在很多最大值类题目里是对的但在乘积题里要小心。假设把 max 或者 min 初始化为0而数组全是负数比如 [-1, -2]那么 max 一开始是0乘以 -1 还是0乘以 -2 还是0最后答案会错误地变成0而不是真正的2。因为0乘以任何数都是0这个“0”像一个污染源会把所有乘积清零。所以滚动变量版最安全的写法是max、min、ans 全部初始化为 nums[0]。这样既避免空数组问题也避免0污染问题。至于“先乘再比较”的交换写法由于它的设计就是在每一轮统一处理当前元素所以 max 和 min 初始化为1是安全的但 ans 必须初始化为 Integer.MIN_VALUE因为它要在循环里收集每一轮的结果。4.3 为什么必须单独维护全局答案 ans动态规划里fMax[i] 表示“以第 i 个元素结尾”的最大乘积但最终答案不一定是最后那个元素结尾的子数组。比如 [2, 3, -2, 4] 里最大乘积 6 是以第1个元素结尾的子数组 [2,3] 产生的而不是以最后一个元素结尾的。所以必须用一个额外的 ans在每一轮迭代中记录历史最大值。这一点和“最长递增子序列”之类的问题很像状态定义是“以 i 结尾”的但答案要扫描所有状态取最大值。如果直接用最后一个 fMax 作为答案遇到最大答案在中间出现的情况就会出错。4.4 滚动更新的先后顺序先算后赋避免污染如果在双变量版里这样写max Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]); min Math.min(Math.min(max * nums[i], min * nums[i]), nums[i]);第二行里的 max 已经是更新过的值了它是“以当前元素结尾的新 max”再拿它去和 min 相乘逻辑就乱了。正确做法是用 curMax 和 curMin 两个局部变量同时保存新值或者先把旧值备份出来。这个坑不亲自踩一次很难注意到因为它不报错只是答案偶尔不对。4.5 关于溢出的思考这道题在LeetCode的数据范围下int 是够用的。但实际面试中如果数组元素很大或者很长乘积可能超过 int 范围。可以提一句“如果数据范围更大把变量类型换成 long或者结合说明使用合适的数据结构”面试官通常会觉得你有工程意识。不过不要过度设计LeetCode 环境里用 int 是标准做法。5. 相似题型与进阶扩展刷一道顶五道5.1 和LeetCode 53题“最大子数组和”的对比把两道题放在一起看是最有效的学习方式。最大子数组和的转移方程只需要一个 dp 值因为加法中负数的符号效应不会反转大小关系。最大子数组乘积则必须维护两个值核心变量是“负负得正带来的大小反转”。对比表格对比项最大子数组和53题乘积最大子数组152题状态数量一个dp即可必须维护max和min两个状态转移方程max(prev cur, cur)max(max(prevMax*cur, prevMin*cur), cur)负数的处理负数只是变小不会反转趋势负数会反转最大值与最小值的角色能否用贪心可以本质上是滚动DP不行必须同时跟踪两个极值这个对比在面试中非常有用。面试官如果先让你写53题然后让你写152题你要能清晰说出“为什么53题的思路不能直接套过来”这比闷头写对代码更分。5.2 进阶变体返回最大乘积子数组本身有时候面试官会追问不只返回最大值还要返回这个子数组。思路是在滚动更新的同时记录边界下标。每当 ans 被更新时记录当前的结束下标同时维护当前最优片段的起始下标。因为负数翻转会让“最优起点”变得复杂通常记录区间的方法是在每次“从当前元素重新开始”时更新候选起点在每次 ans 被更新时固定答案区间。这个代码比纯返回值要长一些但核心逻辑完全一致有兴趣的读者可以自己实现一遍。5.3 其他变体思路还有一类变体是求“乘积最小的连续子数组”只需要把状态转移中 max 和 min 的角色对调其他完全不变。以及考虑环形数组时的最大乘积子数组问题通常做法是拆成两种情况不跨越边界的最大乘积以及跨越边界的情况通过求最小子数组乘积再用总乘积除以最小子数组乘积来得到跨越边界的最大乘积。当然这里要注意除以零的问题遇到0还得单独处理。这些变体没有必要全刷一遍但理解了152题的核心思想后遇到它们都能快速迁移。动态规划题就是这样代码量不大难的是状态定义和不同场景下的变化逻辑吃透一道经典题的价值远大于囫囵吞枣刷十道简单题。我个人在实际练习中的体会是这题第一次做错非常正常重点是要把错误对照着“负负得正”这个本质去复盘。找一个包含正数、负数、零的测试用例把每一步 fMax 和 fMin 都手算出来写一次表格以后再遇到同类题基本就不会慌了。如果面试时能主动讲出“为什么需要两个状态”和“负数如何导致大小反转”这题基本上就拿下了。
