刷动态规划的题最怕碰到这种看着人畜无害、动起手来处处是坑的题。力扣 152 题“乘积最大子数组”就是这样。你拿“53. 最大子数组和”的思路去套很快就翻车因为加法世界里天真的状态定义放到乘法世界里根本不够用。但只要理解了“负数乘负数会反转大小关系”这一条整道题的思路就顺了。这篇文章我按自己从暴力到动态规划、再到各种优化写法的过程来拆。包含完整的 Java 实现、状态转移方程推导、空间优化技巧还有我在本地调试时踩过的具体 Bug。适合准备面试的人看也适合刚学 DP 想搞懂“为什么这题要维护两个状态”的人。代码可以直接改改就跑思路部分我会尽量讲得啰嗦一点因为这类题面试时更看重你能不能把“为什么”讲清楚。1. 题目回顾与直觉陷阱1.1 题目说了什么题目本身很短给定一个整数数组nums找出一个非空连续子数组让它的乘积最大返回这个乘积。子数组必须是连续的不能跳过元素而且至少包含一个元素。几个例子跑一下输入: [2, 3, -2, 4] 输出: 6 解释: 子数组 [2, 3] 乘积为 6最大输入: [-2, 0, -1] 输出: 0 解释: 结果不能为负所以单独的 -1 不是最优[0] 才是输入: [-2] 输出: -2 解释: 只有一个元素只能返回它自己第二个例子尤其适合用来检验初始化逻辑。很多人把答案初始化为0碰上全负数组会直接出错。第三例子则是典型边界数组长度是 1 时不管它是正数还是负数都得原样返回。这题从标签上看是动态规划难度属于中等等级但在面试里出现频率不低。因为它比普通的一维 DP 多拐了一个弯状态不只有一个而是两个并且互相影响。1.2 暴力解法为什么走不通先别急着上 DP暴力解法值得想一遍因为任何优化都是建立在你确实理解“暴力到底慢在哪”的基础上。最直接的暴力就是枚举所有起点和终点然后计算乘积public int maxProduct(int[] nums) { int n nums.length; int ans Integer.MIN_VALUE; for (int i 0; i n; i) { for (int j i; j n; j) { int cur 1; for (int k i; k j; k) { cur * nums[k]; } ans Math.max(ans, cur); } } return ans; }这是 O(n³) 的做法。不过乘积不需要三层循环你可以在扩展终点的时候同步乘上当前元素public int maxProduct(int[] nums) { int n nums.length; int ans Integer.MIN_VALUE; for (int i 0; i n; i) { int cur 1; for (int j i; j n; j) { cur * nums[j]; ans Math.max(ans, cur); } } return ans; }这样降到 O(n²)。听起来不错但题目数组长度通常能到 10⁴ 甚至 10⁵O(n²) 就是亿级运算放在在线评测里基本是超时。更关键的是面试官要考察的就是你能不能写出 O(n) 的解O(n²) 只能算是一个铺垫。暴力解法中其实已经藏了一个 DP 的影子cur * nums[j]本质上就是在复用前一个子数组的乘积。问题在于你把每个起点都重新算了一遍这里面有大量重复计算。如果能把“以某个位置结尾的最大乘积”用一种高效方式递推出来就不需要回头重新枚举起点。2. 动态规划的核心思路2.1 从“最大子数组和”这道师兄弟题说起力扣 53 题“最大子数组和”是绝大多数人接触 DP 的入门题。状态定义很简单dp[i] 以 nums[i] 结尾的子数组的最大和转移方程也清爽dp[i] max(dp[i-1] nums[i], nums[i])翻译成人话对于当前位置i要么把nums[i]接在前面的最优子数组后面要么干脆从nums[i]重新开始。两者取最大。这个状态设计有个隐含前提加法不会改变大小比较的方向。dp[i-1]越大dp[i-1] nums[i]一定越大。你把最大和保存下来对后面的递推永远是“有利”的。乘积就完全不是这么回事了。2.2 乘积的刁钻之处就在“负负得正”假设你还是只维护一个状态以nums[i]结尾的最大乘积。看这个例子nums [-2, 1, -3]按只维护最大值的思路走遍历到-2最大乘积是-2遍历到1候选是-2 * 1 -2和1取1最大变成1遍历到-3候选是1 * -3 -3和-3取-3于是你得到答案1。但肉眼一看就知道[-2, 1, -3]整个子数组的乘积是6这才是正确答案。问题出在哪出在-2这个看起来“没用”的负数被你丢掉了。当后面再遇到一个-3时-2 * 1 * -3可以负负得正变成6。你只保存了“最大”的1却把那个“最小”的-2扔了于是错过了翻身的机会。这就像打牌时你手里攥着一手看起来最烂的牌结果最后一张牌一出来烂牌反而变成王炸。问题是牌局中途你根本不知道什么时候会摸到那张关键牌所以烂牌也得留着。2.3 双状态转移方程与选择逻辑既然“最小值”可能在将来变成“最大值”那就把最小乘积也一并维护起来。定义两个状态maxF[i] 以 nums[i] 结尾的连续子数组的最大乘积 minF[i] 以 nums[i] 结尾的连续子数组的最小乘积minF[i]越负越好这样一旦乘上负数就可以得到很大的正数。转移方程变成maxF[i] max(maxF[i-1] * nums[i], minF[i-1] * nums[i], nums[i]) minF[i] min(maxF[i-1] * nums[i], minF[i-1] * nums[i], nums[i])每一项都跟nums[i]自己比较是因为子数组允许从当前位置重新开始。如果前面的乘积是 0或者乘出来还不如nums[i]单独一个大那就果断切断重来。为什么两个状态可以同步递推因为maxF[i]和minF[i]的候选来源都是nums[i]乘以上一步的两种状态。乘法是可交换的谁乘谁结果一样所以只需要看三种情况取最大或最小。整个递推过程用一个具体例子过一遍nums [2, 3, -2, 4] i0: max2 min2 ans2 i1: maxmax(2*3, 2*3, 3)6 minmin(3, 3, 3)3 ans6 i2: maxmax(6*-2, 3*-2, -2)-2 minmin(6*-2, 3*-2, -2)-12 ans6 i3: maxmax(-2*4, -12*4, 4)4 minmin(-2*4, -12*4, 4)-48 ans6注意i2这一步min变成了-12这个值完全不起眼但一旦后面遇到负数就能立刻翻盘。比如把数组改成[2, 3, -2, -4]i3: maxmax(-2*-4, -12*-4, -4)48 minmin(8, 48, -4)-4 ans48-12 * -4 48最大答案在最后一步才浮出水面。这就是双状态存在的意义。提示状态里存的永远是“以当前下标结尾”的结果所以答案要遍历所有maxF[i]取最大而不是只输出最后一个maxF[n-1]。3. Java 多种实现与细节3.1 最贴近定义的 DP 双数组版先写最清晰、最好解释的版本。两个数组一个存最大一个存最小完全照搬状态转移方程public int maxProduct(int[] nums) { int n nums.length; int[] maxF new int[n]; int[] minF new int[n]; maxF[0] nums[0]; minF[0] nums[0]; int ans nums[0]; for (int i 1; i n; i) { maxF[i] Math.max(maxF[i-1] * nums[i], Math.max(minF[i-1] * nums[i], nums[i])); minF[i] Math.min(maxF[i-1] * nums[i], Math.min(minF[i-1] * nums[i], nums[i])); ans Math.max(ans, maxF[i]); } return ans; }这段代码的优点是每个状态都留了历史记录非常方便调试。你可以在循环里打印maxF[i]和minF[i]逐个位置验证自己的手算结果。一个容易被忽略的细节是maxF[i]和minF[i]的更新虽然是两条赋值语句但maxF[i-1]和minF[i-1]都是上一次循环算好的旧值所以两条语句谁先谁后都没关系。后面滚动变量优化的时候这个“没关系”会变成“非常有关系”。3.2 滚动变量优化O(1) 空间的写法仔细观察状态转移方程i-1时刻的状态只用一次用完就不再需要。所以不需要两个数组用两个临时变量滚动更新就好。public int maxProduct(int[] nums) { int maxF nums[0]; int minF nums[0]; int ans nums[0]; for (int i 1; i nums.length; i) { int mx maxF; int mn minF; maxF Math.max(mx * nums[i], Math.max(mn * nums[i], nums[i])); minF Math.min(mx * nums[i], Math.min(mn * nums[i], nums[i])); ans Math.max(ans, maxF); } return ans; }关键在开头这两行int mx maxF; int mn minF;必须先把旧状态缓存下来。像下面这种写法就是错的maxF Math.max(maxF * nums[i], Math.max(minF * nums[i], nums[i])); minF Math.min(maxF * nums[i], Math.min(minF * nums[i], nums[i]));第二行里的maxF已经被上一行更新成新值了用新值再去算最小乘积整个递推关系就断了。这个 Bug 非常容易犯我一开始写滚动版本时就栽在这里后面第五节会再详细展开。3.3 负数交换小技巧还有一个更精简的写法很多题解里能看到当nums[i] 0时先交换maxF和minF再做统一更新。public int maxProduct(int[] nums) { int maxF nums[0]; int minF nums[0]; int ans nums[0]; for (int i 1; i nums.length; i) { if (nums[i] 0) { int tmp maxF; maxF minF; minF tmp; } maxF Math.max(nums[i], maxF * nums[i]); minF Math.min(nums[i], minF * nums[i]); ans Math.max(ans, maxF); } return ans; }原理也不难理解。max * 负数会变成下一个最小值min * 负数会变成下一个最大值所以乘负数之前把两个变量对调就相当于提前把负数的翻转效果处理掉了之后再统一乘nums[i]即可。这个写法代码短、性能也更好但面试时如果直接甩出来面试官很容易追问“为什么这么做”。建议你练到能用一句话解释清楚再在面试里用它不然老老实实写滚动变量版反而更稳。3.4 双向遍历的另类解法除了 DP还有一种是网上常见的“双向扫描”写法代码量也少public int maxProduct(int[] nums) { int ans nums[0]; int cur 1; for (int i 0; i nums.length; i) { cur * nums[i]; ans Math.max(ans, cur); if (nums[i] 0) { cur 1; } } cur 1; for (int i nums.length - 1; i 0; i--) { cur * nums[i]; ans Math.max(ans, cur); if (nums[i] 0) { cur 1; } } return ans; }思路是把数组按 0 切分成若干段每一段内部没有 0。如果某一段的负数个数是偶数正序扫描就能拿到整段的最大乘积如果负数个数是奇数整段乘起来是负数最大乘积一定出现在“砍掉一侧最边缘负数”之后的某段前缀或后缀里。正序扫描覆盖左半段逆序扫描覆盖右半段两边取最大就不会漏。这个方法可以通过测试但我建议你把它当作“思路拓展”看待而不是首选答案。因为它的正确性不如 DP 直观现场讲解时容易绕晕自己。问就是劝你优先用 DP。4. 复杂度与边界场景分析4.1 三种实现复杂度对比实现方式时间复杂度空间复杂度代码难度适用场景暴力枚举O(n²)O(1)低只用来验证小数据DP 双数组O(n)O(n)中便于调试、讲解思路DP 滚动变量O(n)O(1)中高面试和工程首选负数交换版O(n)O(1)中高追求代码精简时双向遍历O(n)O(1)中思路拓展需要说明的是双向遍历虽然是两次循环但总扫描次数仍是 O(n)常数稍大一点影响可以忽略。四种方式都能过这道题区别在于你能否在现场把思路讲清楚。4.2 边界值与初始化细节这题的初始化有三个坑每一个我都踩过第一个坑ans初始化为0。如果数组全是负数比如[-1, -2]真实答案是2但ans0会在第一次比较时就把正确答案覆盖成 0。正确做法是把ans初始化成nums[0]或者Integer.MIN_VALUE。第二个坑maxF和minF的初始值。很多人都知道要初始化成nums[0]但原因值得说一句状态定义是“以某个下标结尾的最大/最小乘积”第一个位置没有任何前驱状态只能拿nums[0]自己当作状态起点。如果初始化成 0后面所有乘法都会变成 0那就没法玩了。第三个坑数组长度为 1 时。for循环直接从i 1开始根本不会进入所以返回值直接就是nums[0]。这其实是正确的但你要是把循环写成从i 0开始就会把nums[0]重复算一遍导致结果出错。写代码之前先把n 1的情况在脑子里过一遍。另外处理 0 也有一点小讲究。DP 版本的转移方程里maxF[i] max(maxF[i-1] * nums[i], minF[i-1] * nums[i], nums[i])当nums[i] 0时前两项乘积都是 0最后一项nums[i]也是 0所以状态会自然归零。这就是为什么 DP 不需要额外处理 0。而双向遍历的版本遇到 0 必须手动把cur重置为 1否则会把 0 带进下一段乘积。5. 常见问题与避坑记录5.1 一个经典 Bug更新顺序我在 3.2 里提到滚动变量版必须用临时变量保存旧状态。这里把错误版本完整写出来你们看看能不能一眼发现问题public int maxProduct(int[] nums) { int maxF nums[0]; int minF nums[0]; int ans nums[0]; for (int i 1; i nums.length; i) { maxF Math.max(maxF * nums[i], Math.max(minF * nums[i], nums[i])); minF Math.min(maxF * nums[i], Math.min(minF * nums[i], nums[i])); ans Math.max(ans, maxF); } return ans; }问题在第二行minF的更新它用到的maxF已经是当前轮次更新过的新值而不是上一轮的旧值。原本应该用旧 maxF * nums[i]参与最小值的候选结果变成了新 maxF * nums[i]状态递推直接错乱。这种 Bug 用具体数组最容易暴露。比如nums [2, -1, -1]错误版本会算出3正确结果应该是2。排查方法也简单把每个位置的maxF、minF逐步打印出来对照手算结果很快就能定位。5.2 进阶如何还原子数组本身有些面试官不满足于只返回乘积会追问“那你能把子数组本身也输出吗”。这是在考察你对状态的掌控程度。思路是给每个状态额外记录起止下标。因为乘积状态跟着maxF和minF一起迁移所以你需要维护四组端点最大状态的起点终点、最小状态的起点终点。转移时按三类情况分别更新如果maxF[i-1] * nums[i]最大那么最大状态的起点继承maxF[i-1]的起点终点是 i如果minF[i-1] * nums[i]最大那么最大状态的起点继承minF[i-1]的起点终点是 i如果nums[i]自己最大那么起点终点都是 i。最小状态的更新逻辑完全对称。代码写起来不复杂但维护四个起点终点变量下标很容易错位。我建议你把“返回乘积”的版本先写好再在这个基础上扩展下标记录不要想着一步到位。面试时如果时间紧把这个过程用文字讲清楚比吭哧吭哧写完一套带下标的代码更能体现你的思路。5.3 高频面试追问速答这题在面试里经常带着几个追问我把高频问题整理成速查问题一为什么不能只用最大值状态答案负数乘负数的场景下当前的最小值可能变成未来的最大值。只保留最大值会把潜在的翻身机会丢掉所以必须同时保留最小值。问题二为什么要求max的候选里要单独比较nums[i]答案因为子数组可以不跟前面连起来。当nums[i-1]为 0或者前面的乘积小于nums[i]本身时从当前位置重新开始才是最优解。问题三数组里有 0 怎么办答案DP 状态更新里自然会把乘积归零然后靠nums[i]自己重新起一段。不需要额外处理这正是 DP 方程设计得好的地方。问题四如果数组里包含负数、0、正数以外的数比如小数呢答案DP 只涉及乘法和比较不依赖整数性质。只要类型支持乘法运算逻辑同样适用。问题五时间复杂度还能再优化吗答案线性复杂度已经是最优因为至少要遍历一遍数组才能确定每个位置的影响。更快的方案不存在。结束语我个人刷这道题的经验是先写 DP 双数组版本把状态转移讲顺再优化成滚动变量最后再去碰负数交换那种精简写法。顺序反了容易把自己绕进去也会让面试官觉得你在背题。另一个小技巧是遇到任何 DP 题先在纸上把状态定义写清楚然后手动跑一个包含负数和的数组再打开编辑器写代码。亲手推一遍递推过程比看过十篇题解都管用。我第一次手推数组[2, -1, -1]时就发现滚动版本少了临时变量导致结果不对这种即时反馈比事后调试记忆深刻得多。这题背后那个“保留最小值等待负数翻盘”的思路很多同类题都能复用。遇到类似的最大乘积、异或最大子数组之类的问题第一反应都可以是先想想这个运算是否会让“小值”将来变成“大值”。如果会那就老老实实维护两个状态。希望这篇整理能帮你们少踩一点我之前踩过的坑。
刷动态规划的题最怕碰到这种看着人畜无害、动起手来处处是坑的题。力扣 152 题“乘积最大子数组”就是这样。你拿“53. 最大子数组和”的思路去套很快就翻车因为加法世界里天真的状态定义放到乘法世界里根本不够用。但只要理解了“负数乘负数会反转大小关系”这一条整道题的思路就顺了。这篇文章我按自己从暴力到动态规划、再到各种优化写法的过程来拆。包含完整的 Java 实现、状态转移方程推导、空间优化技巧还有我在本地调试时踩过的具体 Bug。适合准备面试的人看也适合刚学 DP 想搞懂“为什么这题要维护两个状态”的人。代码可以直接改改就跑思路部分我会尽量讲得啰嗦一点因为这类题面试时更看重你能不能把“为什么”讲清楚。1. 题目回顾与直觉陷阱1.1 题目说了什么题目本身很短给定一个整数数组nums找出一个非空连续子数组让它的乘积最大返回这个乘积。子数组必须是连续的不能跳过元素而且至少包含一个元素。几个例子跑一下输入: [2, 3, -2, 4] 输出: 6 解释: 子数组 [2, 3] 乘积为 6最大输入: [-2, 0, -1] 输出: 0 解释: 结果不能为负所以单独的 -1 不是最优[0] 才是输入: [-2] 输出: -2 解释: 只有一个元素只能返回它自己第二个例子尤其适合用来检验初始化逻辑。很多人把答案初始化为0碰上全负数组会直接出错。第三例子则是典型边界数组长度是 1 时不管它是正数还是负数都得原样返回。这题从标签上看是动态规划难度属于中等等级但在面试里出现频率不低。因为它比普通的一维 DP 多拐了一个弯状态不只有一个而是两个并且互相影响。1.2 暴力解法为什么走不通先别急着上 DP暴力解法值得想一遍因为任何优化都是建立在你确实理解“暴力到底慢在哪”的基础上。最直接的暴力就是枚举所有起点和终点然后计算乘积public int maxProduct(int[] nums) { int n nums.length; int ans Integer.MIN_VALUE; for (int i 0; i n; i) { for (int j i; j n; j) { int cur 1; for (int k i; k j; k) { cur * nums[k]; } ans Math.max(ans, cur); } } return ans; }这是 O(n³) 的做法。不过乘积不需要三层循环你可以在扩展终点的时候同步乘上当前元素public int maxProduct(int[] nums) { int n nums.length; int ans Integer.MIN_VALUE; for (int i 0; i n; i) { int cur 1; for (int j i; j n; j) { cur * nums[j]; ans Math.max(ans, cur); } } return ans; }这样降到 O(n²)。听起来不错但题目数组长度通常能到 10⁴ 甚至 10⁵O(n²) 就是亿级运算放在在线评测里基本是超时。更关键的是面试官要考察的就是你能不能写出 O(n) 的解O(n²) 只能算是一个铺垫。暴力解法中其实已经藏了一个 DP 的影子cur * nums[j]本质上就是在复用前一个子数组的乘积。问题在于你把每个起点都重新算了一遍这里面有大量重复计算。如果能把“以某个位置结尾的最大乘积”用一种高效方式递推出来就不需要回头重新枚举起点。2. 动态规划的核心思路2.1 从“最大子数组和”这道师兄弟题说起力扣 53 题“最大子数组和”是绝大多数人接触 DP 的入门题。状态定义很简单dp[i] 以 nums[i] 结尾的子数组的最大和转移方程也清爽dp[i] max(dp[i-1] nums[i], nums[i])翻译成人话对于当前位置i要么把nums[i]接在前面的最优子数组后面要么干脆从nums[i]重新开始。两者取最大。这个状态设计有个隐含前提加法不会改变大小比较的方向。dp[i-1]越大dp[i-1] nums[i]一定越大。你把最大和保存下来对后面的递推永远是“有利”的。乘积就完全不是这么回事了。2.2 乘积的刁钻之处就在“负负得正”假设你还是只维护一个状态以nums[i]结尾的最大乘积。看这个例子nums [-2, 1, -3]按只维护最大值的思路走遍历到-2最大乘积是-2遍历到1候选是-2 * 1 -2和1取1最大变成1遍历到-3候选是1 * -3 -3和-3取-3于是你得到答案1。但肉眼一看就知道[-2, 1, -3]整个子数组的乘积是6这才是正确答案。问题出在哪出在-2这个看起来“没用”的负数被你丢掉了。当后面再遇到一个-3时-2 * 1 * -3可以负负得正变成6。你只保存了“最大”的1却把那个“最小”的-2扔了于是错过了翻身的机会。这就像打牌时你手里攥着一手看起来最烂的牌结果最后一张牌一出来烂牌反而变成王炸。问题是牌局中途你根本不知道什么时候会摸到那张关键牌所以烂牌也得留着。2.3 双状态转移方程与选择逻辑既然“最小值”可能在将来变成“最大值”那就把最小乘积也一并维护起来。定义两个状态maxF[i] 以 nums[i] 结尾的连续子数组的最大乘积 minF[i] 以 nums[i] 结尾的连续子数组的最小乘积minF[i]越负越好这样一旦乘上负数就可以得到很大的正数。转移方程变成maxF[i] max(maxF[i-1] * nums[i], minF[i-1] * nums[i], nums[i]) minF[i] min(maxF[i-1] * nums[i], minF[i-1] * nums[i], nums[i])每一项都跟nums[i]自己比较是因为子数组允许从当前位置重新开始。如果前面的乘积是 0或者乘出来还不如nums[i]单独一个大那就果断切断重来。为什么两个状态可以同步递推因为maxF[i]和minF[i]的候选来源都是nums[i]乘以上一步的两种状态。乘法是可交换的谁乘谁结果一样所以只需要看三种情况取最大或最小。整个递推过程用一个具体例子过一遍nums [2, 3, -2, 4] i0: max2 min2 ans2 i1: maxmax(2*3, 2*3, 3)6 minmin(3, 3, 3)3 ans6 i2: maxmax(6*-2, 3*-2, -2)-2 minmin(6*-2, 3*-2, -2)-12 ans6 i3: maxmax(-2*4, -12*4, 4)4 minmin(-2*4, -12*4, 4)-48 ans6注意i2这一步min变成了-12这个值完全不起眼但一旦后面遇到负数就能立刻翻盘。比如把数组改成[2, 3, -2, -4]i3: maxmax(-2*-4, -12*-4, -4)48 minmin(8, 48, -4)-4 ans48-12 * -4 48最大答案在最后一步才浮出水面。这就是双状态存在的意义。提示状态里存的永远是“以当前下标结尾”的结果所以答案要遍历所有maxF[i]取最大而不是只输出最后一个maxF[n-1]。3. Java 多种实现与细节3.1 最贴近定义的 DP 双数组版先写最清晰、最好解释的版本。两个数组一个存最大一个存最小完全照搬状态转移方程public int maxProduct(int[] nums) { int n nums.length; int[] maxF new int[n]; int[] minF new int[n]; maxF[0] nums[0]; minF[0] nums[0]; int ans nums[0]; for (int i 1; i n; i) { maxF[i] Math.max(maxF[i-1] * nums[i], Math.max(minF[i-1] * nums[i], nums[i])); minF[i] Math.min(maxF[i-1] * nums[i], Math.min(minF[i-1] * nums[i], nums[i])); ans Math.max(ans, maxF[i]); } return ans; }这段代码的优点是每个状态都留了历史记录非常方便调试。你可以在循环里打印maxF[i]和minF[i]逐个位置验证自己的手算结果。一个容易被忽略的细节是maxF[i]和minF[i]的更新虽然是两条赋值语句但maxF[i-1]和minF[i-1]都是上一次循环算好的旧值所以两条语句谁先谁后都没关系。后面滚动变量优化的时候这个“没关系”会变成“非常有关系”。3.2 滚动变量优化O(1) 空间的写法仔细观察状态转移方程i-1时刻的状态只用一次用完就不再需要。所以不需要两个数组用两个临时变量滚动更新就好。public int maxProduct(int[] nums) { int maxF nums[0]; int minF nums[0]; int ans nums[0]; for (int i 1; i nums.length; i) { int mx maxF; int mn minF; maxF Math.max(mx * nums[i], Math.max(mn * nums[i], nums[i])); minF Math.min(mx * nums[i], Math.min(mn * nums[i], nums[i])); ans Math.max(ans, maxF); } return ans; }关键在开头这两行int mx maxF; int mn minF;必须先把旧状态缓存下来。像下面这种写法就是错的maxF Math.max(maxF * nums[i], Math.max(minF * nums[i], nums[i])); minF Math.min(maxF * nums[i], Math.min(minF * nums[i], nums[i]));第二行里的maxF已经被上一行更新成新值了用新值再去算最小乘积整个递推关系就断了。这个 Bug 非常容易犯我一开始写滚动版本时就栽在这里后面第五节会再详细展开。3.3 负数交换小技巧还有一个更精简的写法很多题解里能看到当nums[i] 0时先交换maxF和minF再做统一更新。public int maxProduct(int[] nums) { int maxF nums[0]; int minF nums[0]; int ans nums[0]; for (int i 1; i nums.length; i) { if (nums[i] 0) { int tmp maxF; maxF minF; minF tmp; } maxF Math.max(nums[i], maxF * nums[i]); minF Math.min(nums[i], minF * nums[i]); ans Math.max(ans, maxF); } return ans; }原理也不难理解。max * 负数会变成下一个最小值min * 负数会变成下一个最大值所以乘负数之前把两个变量对调就相当于提前把负数的翻转效果处理掉了之后再统一乘nums[i]即可。这个写法代码短、性能也更好但面试时如果直接甩出来面试官很容易追问“为什么这么做”。建议你练到能用一句话解释清楚再在面试里用它不然老老实实写滚动变量版反而更稳。3.4 双向遍历的另类解法除了 DP还有一种是网上常见的“双向扫描”写法代码量也少public int maxProduct(int[] nums) { int ans nums[0]; int cur 1; for (int i 0; i nums.length; i) { cur * nums[i]; ans Math.max(ans, cur); if (nums[i] 0) { cur 1; } } cur 1; for (int i nums.length - 1; i 0; i--) { cur * nums[i]; ans Math.max(ans, cur); if (nums[i] 0) { cur 1; } } return ans; }思路是把数组按 0 切分成若干段每一段内部没有 0。如果某一段的负数个数是偶数正序扫描就能拿到整段的最大乘积如果负数个数是奇数整段乘起来是负数最大乘积一定出现在“砍掉一侧最边缘负数”之后的某段前缀或后缀里。正序扫描覆盖左半段逆序扫描覆盖右半段两边取最大就不会漏。这个方法可以通过测试但我建议你把它当作“思路拓展”看待而不是首选答案。因为它的正确性不如 DP 直观现场讲解时容易绕晕自己。问就是劝你优先用 DP。4. 复杂度与边界场景分析4.1 三种实现复杂度对比实现方式时间复杂度空间复杂度代码难度适用场景暴力枚举O(n²)O(1)低只用来验证小数据DP 双数组O(n)O(n)中便于调试、讲解思路DP 滚动变量O(n)O(1)中高面试和工程首选负数交换版O(n)O(1)中高追求代码精简时双向遍历O(n)O(1)中思路拓展需要说明的是双向遍历虽然是两次循环但总扫描次数仍是 O(n)常数稍大一点影响可以忽略。四种方式都能过这道题区别在于你能否在现场把思路讲清楚。4.2 边界值与初始化细节这题的初始化有三个坑每一个我都踩过第一个坑ans初始化为0。如果数组全是负数比如[-1, -2]真实答案是2但ans0会在第一次比较时就把正确答案覆盖成 0。正确做法是把ans初始化成nums[0]或者Integer.MIN_VALUE。第二个坑maxF和minF的初始值。很多人都知道要初始化成nums[0]但原因值得说一句状态定义是“以某个下标结尾的最大/最小乘积”第一个位置没有任何前驱状态只能拿nums[0]自己当作状态起点。如果初始化成 0后面所有乘法都会变成 0那就没法玩了。第三个坑数组长度为 1 时。for循环直接从i 1开始根本不会进入所以返回值直接就是nums[0]。这其实是正确的但你要是把循环写成从i 0开始就会把nums[0]重复算一遍导致结果出错。写代码之前先把n 1的情况在脑子里过一遍。另外处理 0 也有一点小讲究。DP 版本的转移方程里maxF[i] max(maxF[i-1] * nums[i], minF[i-1] * nums[i], nums[i])当nums[i] 0时前两项乘积都是 0最后一项nums[i]也是 0所以状态会自然归零。这就是为什么 DP 不需要额外处理 0。而双向遍历的版本遇到 0 必须手动把cur重置为 1否则会把 0 带进下一段乘积。5. 常见问题与避坑记录5.1 一个经典 Bug更新顺序我在 3.2 里提到滚动变量版必须用临时变量保存旧状态。这里把错误版本完整写出来你们看看能不能一眼发现问题public int maxProduct(int[] nums) { int maxF nums[0]; int minF nums[0]; int ans nums[0]; for (int i 1; i nums.length; i) { maxF Math.max(maxF * nums[i], Math.max(minF * nums[i], nums[i])); minF Math.min(maxF * nums[i], Math.min(minF * nums[i], nums[i])); ans Math.max(ans, maxF); } return ans; }问题在第二行minF的更新它用到的maxF已经是当前轮次更新过的新值而不是上一轮的旧值。原本应该用旧 maxF * nums[i]参与最小值的候选结果变成了新 maxF * nums[i]状态递推直接错乱。这种 Bug 用具体数组最容易暴露。比如nums [2, -1, -1]错误版本会算出3正确结果应该是2。排查方法也简单把每个位置的maxF、minF逐步打印出来对照手算结果很快就能定位。5.2 进阶如何还原子数组本身有些面试官不满足于只返回乘积会追问“那你能把子数组本身也输出吗”。这是在考察你对状态的掌控程度。思路是给每个状态额外记录起止下标。因为乘积状态跟着maxF和minF一起迁移所以你需要维护四组端点最大状态的起点终点、最小状态的起点终点。转移时按三类情况分别更新如果maxF[i-1] * nums[i]最大那么最大状态的起点继承maxF[i-1]的起点终点是 i如果minF[i-1] * nums[i]最大那么最大状态的起点继承minF[i-1]的起点终点是 i如果nums[i]自己最大那么起点终点都是 i。最小状态的更新逻辑完全对称。代码写起来不复杂但维护四个起点终点变量下标很容易错位。我建议你把“返回乘积”的版本先写好再在这个基础上扩展下标记录不要想着一步到位。面试时如果时间紧把这个过程用文字讲清楚比吭哧吭哧写完一套带下标的代码更能体现你的思路。5.3 高频面试追问速答这题在面试里经常带着几个追问我把高频问题整理成速查问题一为什么不能只用最大值状态答案负数乘负数的场景下当前的最小值可能变成未来的最大值。只保留最大值会把潜在的翻身机会丢掉所以必须同时保留最小值。问题二为什么要求max的候选里要单独比较nums[i]答案因为子数组可以不跟前面连起来。当nums[i-1]为 0或者前面的乘积小于nums[i]本身时从当前位置重新开始才是最优解。问题三数组里有 0 怎么办答案DP 状态更新里自然会把乘积归零然后靠nums[i]自己重新起一段。不需要额外处理这正是 DP 方程设计得好的地方。问题四如果数组里包含负数、0、正数以外的数比如小数呢答案DP 只涉及乘法和比较不依赖整数性质。只要类型支持乘法运算逻辑同样适用。问题五时间复杂度还能再优化吗答案线性复杂度已经是最优因为至少要遍历一遍数组才能确定每个位置的影响。更快的方案不存在。结束语我个人刷这道题的经验是先写 DP 双数组版本把状态转移讲顺再优化成滚动变量最后再去碰负数交换那种精简写法。顺序反了容易把自己绕进去也会让面试官觉得你在背题。另一个小技巧是遇到任何 DP 题先在纸上把状态定义写清楚然后手动跑一个包含负数和的数组再打开编辑器写代码。亲手推一遍递推过程比看过十篇题解都管用。我第一次手推数组[2, -1, -1]时就发现滚动版本少了临时变量导致结果不对这种即时反馈比事后调试记忆深刻得多。这题背后那个“保留最小值等待负数翻盘”的思路很多同类题都能复用。遇到类似的最大乘积、异或最大子数组之类的问题第一反应都可以是先想想这个运算是否会让“小值”将来变成“大值”。如果会那就老老实实维护两个状态。希望这篇整理能帮你们少踩一点我之前踩过的坑。
