东华大学OJ第39题“最大乘积”做过的同学都知道这题表面上是道动态规划入门题实际上是个暗藏杀机的陷阱题。我第一次提交的时候信誓旦旦觉得自己写对了结果WA了好几次最后才意识到这题跟常规的“最大子数组和”根本不是一个物种。今天我就把这题的来龙去脉、正解思路、代码实现和踩坑经验一次说清楚给正在刷OJ的学弟学妹们做个参考。在线编程与OJ评测系统普及之后像东华大学OJ这样的平台成了无数计算机专业学生从入门到放弃的第一站。题目编号39看起来平平无奇但“最大乘积”这四个字背后藏着动态规划里一个极其经典的思维转变状态不仅要记录“最大值”还得记录“最小值”。这题搞懂了后面再遇到什么“乘积最大子数组”“最大子序列”之类的变种题你都能一眼看穿出题人的小心思。1. 题目到底在考什么一个比“最大和”更阴险的兄弟题1.1 在线编程与OJ评测系统里的经典题型先说说这题所处的场景。OJ系统Online Judge在线评测系统是计算机专业学生刷算法题的主要阵地这类平台的特点是提交代码后系统自动用一组测试数据去跑你的程序每个测试点都必须通过才能拿到AC。不能AC就等于白做所以OJ刷题培养的不仅是“把题解出来”的能力更是“把题在各种边界条件下写对”的能力。东华大学OJ的39题“最大乘积”题目描述很简短给一个整数数组找出乘积最大的连续子数组返回这个最大乘积。这个“连续”二字是重点但也是最容易被忽略的地方。它不是让你求整个数组所有元素相乘的结果而是你必须从数组中截取一段连续区间使得这一段区间内所有整数的乘积最大。这类题目在各大OJ里都是常客因为它在动态规划的教学链条里卡在一个很巧妙的位置。前面通常有“最大子数组和”LeetCode 53很多人做完那个题以后会很自然地想最大乘积不就是把加法换成乘法吗然后兴致勃勃地写了个“只维护当前最大乘积”的版本一提交WA。恭喜踩坑。1.2 加法思维和乘法思维的本质差异先看一个最简单的例子数组[-2, 3, -4]。这个数组的最大子数组和是多少用“最大子数组和”的经典DP算法答案是3——因为 -2 3 13 (-4) -1都不如单独取3大。但最大乘积是多少答案是24因为(-2) × 3 × (-4) 24。注意最后这个数字是从左到右全部乘起来才得到的。这就是加法和乘法的本质差异加法里负数只会让和变小所以遇到负数直接“丢弃”就好乘法里负数乘以负数会变成正数两个看起来很小的负数乘在一起反而可能得到最大的正数。换句话说在计算最大乘积的过程中你不仅要关心“当前乘积最大是多少”还必须关心“当前乘积最小是多少”。因为当前这个最小值如果下一步又碰到一个负数它俩一乘最小值就直接翻身变成最大值了。这就是整道题的核心思维转折点动态规划状态里必须同时维护最大值和最小值两个状态。2. 思路拆解从暴力到动态规划的“为什么”2.1 暴力枚举为什么不可行先看最朴素的做法枚举所有可能的连续子数组逐个计算乘积取最大值。代码写起来倒是简单# 伪代码示意 max_val -float(inf) for i in range(len(nums)): cur 1 for j in range(i, len(nums)): cur * nums[j] max_val max(max_val, cur)总共两层循环时间复杂度是O(n²)。如果数组长度是10万这就需要100亿次乘法运算OJ的时限一般是1秒稳稳的超时。就算你把内层循环优化一下比如遇到0就提前break最坏情况下依然是指数级的端点组合。O(n²)的时间复杂度在大多数OJ题目里都是被判死刑的。所以必须把思路从“枚举所有子数组”切换到“利用已知信息递推”这就是动态规划的切入角度。2.2 两个状态缺一不可动态规划的核心是“用之前算过的结果推出当前的结果”。对于最大子数组和问题状态转移方程是dp[i] max(nums[i], dp[i-1] nums[i])dp[i]表示以第i个元素结尾的子数组的最大和。它只有两种选择从当前位置重新开始nums[i]或者跟前面的最大和拼接dp[i-1] nums[i]。如果把加法换成乘法很多人会写# 这版是错的 dp[i] max(nums[i], dp[i-1] * nums[i])这个式子在数组为正数的场景下没问题一旦出现负数就崩了。比如[-2, 3, -4]按这个式子算i0dp[0] -2i1dp[1] max(3, -2×3) max(3, -6) 3i2dp[2] max(-4, 3×(-4)) max(-4, -12) -4最终答案判成3而正确答案是24。问题出在哪出在dp[1]只记录了“到位置1为止的最大乘积3”但忽略了“到位置1为止的最小乘积-6”。当位置2的-4到来时-6 × (-4) 24才是正解可你在状态里根本没保存这-6。所以正解的状态必须是两个maxF[i]以 nums[i] 结尾的子数组的最大乘积 minF[i]以 nums[i] 结尾的子数组的最小乘积每到一个新位置nums[i]我们做三类比较重新开始只取 nums[i]和之前的maxF相乘maxF[i-1] × nums[i]和之前的minF相乘minF[i-1] × nums[i]maxF取这三者的最大值minF取这三者的最小值。为什么minF也要参与因为minF往往是负数再乘以当前的负数就可能变成最大的正数。2.3 为什么必须暂存“上一个状态的旧值”这里有个特别容易翻车的实现细节在计算第i个位置时maxF[i]和minF[i]都依赖于maxF[i-1]和minF[i-1]也就是上一轮的“旧值”。如果你直接原地更新maxF max(nums[i], maxF * nums[i], minF * nums[i]) minF min(nums[i], maxF * nums[i], minF * nums[i]) # 这里maxF已经被更新了第二行里的maxF已经变成新值了用它去算minF就相当于在用当前轮的结果计算当前轮的结果逻辑完全乱套。正确做法是先保存上一轮的旧值或者用临时变量同时计算两个新值。这个“暂存旧值”的细节在实际编码中比理论推导更容易出错。我见过不少同学理论上懂但一写代码就写错。后面第3章我会给出完整的正确写法你可以直接对照着看。3. 实操过程与核心环节实现3.1 C版本从思路到可AC代码这题最主流的写法是C因为东华大学OJ的很多算法课程就是用C/C教学的。直接上代码class Solution { public: int maxProduct(vectorint nums) { // 以当前元素结尾的最大乘积和最小乘积 int maxF nums[0]; int minF nums[0]; int ans nums[0]; for (int i 1; i nums.size(); i) { // 先保存上一轮的值防止覆盖导致逻辑错误 int mx maxF; int mn minF; maxF max(nums[i], max(mx * nums[i], mn * nums[i])); minF min(nums[i], min(mx * nums[i], mn * nums[i])); ans max(ans, maxF); } return ans; } };这段代码的关键点有三个逐一说清楚。第一maxF和minF的初始值都设为nums[0]。有些同学习惯初始化为0或者INT_MAX这在这里会出问题。如果初始化为0而数组第一个元素是负数maxF会错误地变成0如果初始化为INT_MAX或INT_MIN在做乘法的时候可能直接溢出。正确做法就是老老实实用第一个元素初始化。第二mx和mn这两个临时变量是灵魂。它们保存的是第i-1轮的状态也就是旧值。在真正更新maxF和minF之前这两玩意儿不能丢。举一个具体例子nums [2, -5, -3]。初始时maxF2minF2。i1时cur-5mx2mn2。maxF max(-5, -10, -10) -5minF min(-5, -10, -10) -10。i2时cur-3mx-5mn-10。maxF max(-3, 15, 30) 30minF min(-3, -15, -10) -15。ans30正确。如果不用临时变量更新完maxF后再算minF那么minF会用到刚刚更新过的maxF旧值结果就会错。第三ans每轮都要更新为maxF的最大值。因为最大值不一定出现在数组末尾可能出现在中间的某个位置。比如数组[1, 2, 3, 0, 0]最大乘积6出现在下标2遍历到后面的0时maxF变成了0但正确答案仍是6。所以ans要始终记录历史最大值。3.2 Python版本同样的逻辑更简洁的写法Python版本逻辑完全一致只是语法略有不同。如果你在OJ上用Python提交可以直接用下面这段from typing import List class Solution: def maxProduct(self, nums: List[int]) - int: max_f nums[0] min_f nums[0] ans nums[0] for num in nums[1:]: # 保留旧值 mx, mn max_f, min_f # 更新最大值可能是当前元素本身、最大值乘当前元素、最小值乘当前元素 max_f max(num, mx * num, mn * num) # 更新最小值同理 min_f min(num, mx * num, mn * num) ans max(ans, max_f) return ans这版代码和C版本一一对应没有任何多余的复杂处理。值得一提的是Python里max和min可以一次传入三个参数写起来比C的嵌套max简洁不少。3.3 边界条件与测试用例刷OJ只写代码不做边界测试等于白刷。我总结了几个必须验证的边界场景直接做成表格给你对照测试用例预期结果为什么[3, -1, 4]4中间的正数组合乘积最大是4只取4而不是3×(-1)×4-12[-2, 0, -1]0包含0最大乘积是0[-2, -3, -1]6(-2)×(-3)6这是最大正乘积[0, 0, 0]0全0数组答案不能为负[-1]-1只有一个负数只能取它本身[2, 3, -2, 4]6经典用例最大子数组是[2,3]尤其要注意全负数场景。比如[-1, -2, -3]正确答案是6也就是取前两个负数的乘积。很多同学以为全负数数组的答案就是最大的那个数那是绝对错误的。有了minF这个状态负数乘以负数就能算出正数。4. 常见错误与排查技巧实录4.1 只维护最大值最典型的翻车现场这是90%的人第一次提交会掉的坑。写法看起来逻辑自洽// 错误示范 int maxF nums[0], ans nums[0]; for (int i 1; i nums.size(); i) { maxF max(nums[i], maxF * nums[i]); ans max(ans, maxF); }用[-2, 3, -4]一测就露馅。因为maxF丢掉了负数状态-6导致后续的-4无法翻身。这类错误在OJ上表现就是“部分测试点WA错误答案”但案例太小又看不出来非常难排查。我的排查建议是WA的时候别急着看别人的题解先用几个手工构造的负负得正用例测一遍自己的程序80%的问题当场就能暴露。4.2 初始值设置错误把ans设成0还有一种经典错误是把ans初始化为0int ans 0; // 错误示范如果数组全是负数比如[-3, -2, -1]正确答案是6但程序遍历过程中ans一开始就是0永远大于任何负数乘积最后输出0。这种错误的隐蔽性极高因为你用正数数组测永远测不出来。记住一条铁律涉及乘积类的极值问题初始值要么设为第一个元素要么设为INT_MIN千万别默认设为0。4.3 覆盖顺序问题更新顺序错了逻辑全乱在第2章末尾我已经提过“暂存旧值”的问题这里用一个更直观的版本再演示一下错误# 错误示范max_f更新后min_f的计算被污染 max_f max(num, max_f * num, min_f * num) min_f min(num, max_f * num, min_f * num) # 此时max_f是新的了这种写法在nums [2, -3, -4]上测试会得到错误答案。为什么因为第二个min_f计算时用到的max_f已经是本轮更新后的新值它失去了和上一轮max_f的组合可能。用临时变量或者一行同时赋值都能解决这个问题我个人的习惯是写临时变量可读性更好。4.4 除了动态规划还有别的解法吗刷题久了你会发现同一个知识点可以有多种切入角度。这题除了DP还有一个“按0分段”的数学思路把数组按0切开每一段里没有0那么乘积的绝对值会随着长度增加单调递增不考虑符号时。这时最大乘积只可能是三种情况整段乘积、去掉这一段最左边负数后的乘积、去掉这一段最右边负数后的乘积。因为如果整段乘积是负数去掉一个负数就能变正如果整段乘积是正数那整段就是答案如果负数个数为偶数整段必为正直接取整段。这个思路不需要DP只需要一次线性扫描加少量前缀乘积也是O(n)时间代码写起来甚至更短。不过实际面试和考试中DP版是被广泛认可的通用解因为它不需要考虑各种分段细节思维量更低而且遇到0也能自动处理。我的建议是考试写DP稳平时训练可以拿“按0分段”的思路来验证自己对负数规律的理解。4.5 大数溢出问题的提醒最后说一个很多人忽略的细节int型的溢出。数组里的元素可以在[-1000, 1000]级别如果数组很长且正数很多中间过程的乘积很可能超过int的范围。这题的测试数据如果比较温和int勉强够用如果数据比较极限建议直接用long long保存maxF和minF。C里定义成long long maxF nums[0]基本上就能避开溢出问题。Python不涉及这个因为Python的整数可以无限大。我在实际测试中遇到过一组数据[1000, 1000, 1000, 1000, 1000]int版直接溢出为负数导致答案错误。这个坑特别隐蔽因为溢出结果看起来像是一个正常的负数你的程序不会崩但就是WA。所以只要乘积题我第一反应就是开long long这已经是肌肉记忆了。5. 从这道题延伸出去一个思路解决一类题这题做完之后你会发现一个特别有意思的现象动态规划的状态设计不是拍脑袋想出来的而是根据“当前选择会受到哪些历史因素的影响”来确定的。最大子数组和只受“历史最大值”影响所以一个状态够用最大乘积同时受“历史最大值”和“历史最小值”影响所以必须两个状态。把这种思维方式迁移出去你就可以解决一系列“看起来差不多但其实完全不一样”的题目。比如求最大绝对值的连续子数组、求乘积为正数的最长子数组长度、求加减交替的最长子序列……这些题的共性都是状态转移时你不仅要考虑“最优状态”还要考虑“最劣状态”。因为最劣状态在某些条件下会翻转成最优状态。我个人的学习心得是做OJ题不能只看AC了没有你得学会“给自己出题”。比如这题AC了你可以改一改“如果允许跳过而不是丢弃0答案会怎样变化”“如果数组长度达到10的6次方空间复杂度能否从O(1)降到O(1)要不要开数组”这种头脑实验比盲目刷下一题有用得多。最后分享一个小技巧是我刷了上百道DP题之后总结出来的遇到动态规划题先别看题解手工构造五个用例正常用例、全正数、全负数、含0、单个元素在每个用例上把转移过程手推一遍。推不出矛盾说明你的状态设计合理推到一半发现结果不对恭喜你你已经提前发现了隐藏的坑。这道“最大乘积”题只要你能靠手推发现“必须同时维护最大值和最小值”那你的DP基本功就真的过关了。
东华大学OJ第39题“最大乘积”做过的同学都知道这题表面上是道动态规划入门题实际上是个暗藏杀机的陷阱题。我第一次提交的时候信誓旦旦觉得自己写对了结果WA了好几次最后才意识到这题跟常规的“最大子数组和”根本不是一个物种。今天我就把这题的来龙去脉、正解思路、代码实现和踩坑经验一次说清楚给正在刷OJ的学弟学妹们做个参考。在线编程与OJ评测系统普及之后像东华大学OJ这样的平台成了无数计算机专业学生从入门到放弃的第一站。题目编号39看起来平平无奇但“最大乘积”这四个字背后藏着动态规划里一个极其经典的思维转变状态不仅要记录“最大值”还得记录“最小值”。这题搞懂了后面再遇到什么“乘积最大子数组”“最大子序列”之类的变种题你都能一眼看穿出题人的小心思。1. 题目到底在考什么一个比“最大和”更阴险的兄弟题1.1 在线编程与OJ评测系统里的经典题型先说说这题所处的场景。OJ系统Online Judge在线评测系统是计算机专业学生刷算法题的主要阵地这类平台的特点是提交代码后系统自动用一组测试数据去跑你的程序每个测试点都必须通过才能拿到AC。不能AC就等于白做所以OJ刷题培养的不仅是“把题解出来”的能力更是“把题在各种边界条件下写对”的能力。东华大学OJ的39题“最大乘积”题目描述很简短给一个整数数组找出乘积最大的连续子数组返回这个最大乘积。这个“连续”二字是重点但也是最容易被忽略的地方。它不是让你求整个数组所有元素相乘的结果而是你必须从数组中截取一段连续区间使得这一段区间内所有整数的乘积最大。这类题目在各大OJ里都是常客因为它在动态规划的教学链条里卡在一个很巧妙的位置。前面通常有“最大子数组和”LeetCode 53很多人做完那个题以后会很自然地想最大乘积不就是把加法换成乘法吗然后兴致勃勃地写了个“只维护当前最大乘积”的版本一提交WA。恭喜踩坑。1.2 加法思维和乘法思维的本质差异先看一个最简单的例子数组[-2, 3, -4]。这个数组的最大子数组和是多少用“最大子数组和”的经典DP算法答案是3——因为 -2 3 13 (-4) -1都不如单独取3大。但最大乘积是多少答案是24因为(-2) × 3 × (-4) 24。注意最后这个数字是从左到右全部乘起来才得到的。这就是加法和乘法的本质差异加法里负数只会让和变小所以遇到负数直接“丢弃”就好乘法里负数乘以负数会变成正数两个看起来很小的负数乘在一起反而可能得到最大的正数。换句话说在计算最大乘积的过程中你不仅要关心“当前乘积最大是多少”还必须关心“当前乘积最小是多少”。因为当前这个最小值如果下一步又碰到一个负数它俩一乘最小值就直接翻身变成最大值了。这就是整道题的核心思维转折点动态规划状态里必须同时维护最大值和最小值两个状态。2. 思路拆解从暴力到动态规划的“为什么”2.1 暴力枚举为什么不可行先看最朴素的做法枚举所有可能的连续子数组逐个计算乘积取最大值。代码写起来倒是简单# 伪代码示意 max_val -float(inf) for i in range(len(nums)): cur 1 for j in range(i, len(nums)): cur * nums[j] max_val max(max_val, cur)总共两层循环时间复杂度是O(n²)。如果数组长度是10万这就需要100亿次乘法运算OJ的时限一般是1秒稳稳的超时。就算你把内层循环优化一下比如遇到0就提前break最坏情况下依然是指数级的端点组合。O(n²)的时间复杂度在大多数OJ题目里都是被判死刑的。所以必须把思路从“枚举所有子数组”切换到“利用已知信息递推”这就是动态规划的切入角度。2.2 两个状态缺一不可动态规划的核心是“用之前算过的结果推出当前的结果”。对于最大子数组和问题状态转移方程是dp[i] max(nums[i], dp[i-1] nums[i])dp[i]表示以第i个元素结尾的子数组的最大和。它只有两种选择从当前位置重新开始nums[i]或者跟前面的最大和拼接dp[i-1] nums[i]。如果把加法换成乘法很多人会写# 这版是错的 dp[i] max(nums[i], dp[i-1] * nums[i])这个式子在数组为正数的场景下没问题一旦出现负数就崩了。比如[-2, 3, -4]按这个式子算i0dp[0] -2i1dp[1] max(3, -2×3) max(3, -6) 3i2dp[2] max(-4, 3×(-4)) max(-4, -12) -4最终答案判成3而正确答案是24。问题出在哪出在dp[1]只记录了“到位置1为止的最大乘积3”但忽略了“到位置1为止的最小乘积-6”。当位置2的-4到来时-6 × (-4) 24才是正解可你在状态里根本没保存这-6。所以正解的状态必须是两个maxF[i]以 nums[i] 结尾的子数组的最大乘积 minF[i]以 nums[i] 结尾的子数组的最小乘积每到一个新位置nums[i]我们做三类比较重新开始只取 nums[i]和之前的maxF相乘maxF[i-1] × nums[i]和之前的minF相乘minF[i-1] × nums[i]maxF取这三者的最大值minF取这三者的最小值。为什么minF也要参与因为minF往往是负数再乘以当前的负数就可能变成最大的正数。2.3 为什么必须暂存“上一个状态的旧值”这里有个特别容易翻车的实现细节在计算第i个位置时maxF[i]和minF[i]都依赖于maxF[i-1]和minF[i-1]也就是上一轮的“旧值”。如果你直接原地更新maxF max(nums[i], maxF * nums[i], minF * nums[i]) minF min(nums[i], maxF * nums[i], minF * nums[i]) # 这里maxF已经被更新了第二行里的maxF已经变成新值了用它去算minF就相当于在用当前轮的结果计算当前轮的结果逻辑完全乱套。正确做法是先保存上一轮的旧值或者用临时变量同时计算两个新值。这个“暂存旧值”的细节在实际编码中比理论推导更容易出错。我见过不少同学理论上懂但一写代码就写错。后面第3章我会给出完整的正确写法你可以直接对照着看。3. 实操过程与核心环节实现3.1 C版本从思路到可AC代码这题最主流的写法是C因为东华大学OJ的很多算法课程就是用C/C教学的。直接上代码class Solution { public: int maxProduct(vectorint nums) { // 以当前元素结尾的最大乘积和最小乘积 int maxF nums[0]; int minF nums[0]; int ans nums[0]; for (int i 1; i nums.size(); i) { // 先保存上一轮的值防止覆盖导致逻辑错误 int mx maxF; int mn minF; maxF max(nums[i], max(mx * nums[i], mn * nums[i])); minF min(nums[i], min(mx * nums[i], mn * nums[i])); ans max(ans, maxF); } return ans; } };这段代码的关键点有三个逐一说清楚。第一maxF和minF的初始值都设为nums[0]。有些同学习惯初始化为0或者INT_MAX这在这里会出问题。如果初始化为0而数组第一个元素是负数maxF会错误地变成0如果初始化为INT_MAX或INT_MIN在做乘法的时候可能直接溢出。正确做法就是老老实实用第一个元素初始化。第二mx和mn这两个临时变量是灵魂。它们保存的是第i-1轮的状态也就是旧值。在真正更新maxF和minF之前这两玩意儿不能丢。举一个具体例子nums [2, -5, -3]。初始时maxF2minF2。i1时cur-5mx2mn2。maxF max(-5, -10, -10) -5minF min(-5, -10, -10) -10。i2时cur-3mx-5mn-10。maxF max(-3, 15, 30) 30minF min(-3, -15, -10) -15。ans30正确。如果不用临时变量更新完maxF后再算minF那么minF会用到刚刚更新过的maxF旧值结果就会错。第三ans每轮都要更新为maxF的最大值。因为最大值不一定出现在数组末尾可能出现在中间的某个位置。比如数组[1, 2, 3, 0, 0]最大乘积6出现在下标2遍历到后面的0时maxF变成了0但正确答案仍是6。所以ans要始终记录历史最大值。3.2 Python版本同样的逻辑更简洁的写法Python版本逻辑完全一致只是语法略有不同。如果你在OJ上用Python提交可以直接用下面这段from typing import List class Solution: def maxProduct(self, nums: List[int]) - int: max_f nums[0] min_f nums[0] ans nums[0] for num in nums[1:]: # 保留旧值 mx, mn max_f, min_f # 更新最大值可能是当前元素本身、最大值乘当前元素、最小值乘当前元素 max_f max(num, mx * num, mn * num) # 更新最小值同理 min_f min(num, mx * num, mn * num) ans max(ans, max_f) return ans这版代码和C版本一一对应没有任何多余的复杂处理。值得一提的是Python里max和min可以一次传入三个参数写起来比C的嵌套max简洁不少。3.3 边界条件与测试用例刷OJ只写代码不做边界测试等于白刷。我总结了几个必须验证的边界场景直接做成表格给你对照测试用例预期结果为什么[3, -1, 4]4中间的正数组合乘积最大是4只取4而不是3×(-1)×4-12[-2, 0, -1]0包含0最大乘积是0[-2, -3, -1]6(-2)×(-3)6这是最大正乘积[0, 0, 0]0全0数组答案不能为负[-1]-1只有一个负数只能取它本身[2, 3, -2, 4]6经典用例最大子数组是[2,3]尤其要注意全负数场景。比如[-1, -2, -3]正确答案是6也就是取前两个负数的乘积。很多同学以为全负数数组的答案就是最大的那个数那是绝对错误的。有了minF这个状态负数乘以负数就能算出正数。4. 常见错误与排查技巧实录4.1 只维护最大值最典型的翻车现场这是90%的人第一次提交会掉的坑。写法看起来逻辑自洽// 错误示范 int maxF nums[0], ans nums[0]; for (int i 1; i nums.size(); i) { maxF max(nums[i], maxF * nums[i]); ans max(ans, maxF); }用[-2, 3, -4]一测就露馅。因为maxF丢掉了负数状态-6导致后续的-4无法翻身。这类错误在OJ上表现就是“部分测试点WA错误答案”但案例太小又看不出来非常难排查。我的排查建议是WA的时候别急着看别人的题解先用几个手工构造的负负得正用例测一遍自己的程序80%的问题当场就能暴露。4.2 初始值设置错误把ans设成0还有一种经典错误是把ans初始化为0int ans 0; // 错误示范如果数组全是负数比如[-3, -2, -1]正确答案是6但程序遍历过程中ans一开始就是0永远大于任何负数乘积最后输出0。这种错误的隐蔽性极高因为你用正数数组测永远测不出来。记住一条铁律涉及乘积类的极值问题初始值要么设为第一个元素要么设为INT_MIN千万别默认设为0。4.3 覆盖顺序问题更新顺序错了逻辑全乱在第2章末尾我已经提过“暂存旧值”的问题这里用一个更直观的版本再演示一下错误# 错误示范max_f更新后min_f的计算被污染 max_f max(num, max_f * num, min_f * num) min_f min(num, max_f * num, min_f * num) # 此时max_f是新的了这种写法在nums [2, -3, -4]上测试会得到错误答案。为什么因为第二个min_f计算时用到的max_f已经是本轮更新后的新值它失去了和上一轮max_f的组合可能。用临时变量或者一行同时赋值都能解决这个问题我个人的习惯是写临时变量可读性更好。4.4 除了动态规划还有别的解法吗刷题久了你会发现同一个知识点可以有多种切入角度。这题除了DP还有一个“按0分段”的数学思路把数组按0切开每一段里没有0那么乘积的绝对值会随着长度增加单调递增不考虑符号时。这时最大乘积只可能是三种情况整段乘积、去掉这一段最左边负数后的乘积、去掉这一段最右边负数后的乘积。因为如果整段乘积是负数去掉一个负数就能变正如果整段乘积是正数那整段就是答案如果负数个数为偶数整段必为正直接取整段。这个思路不需要DP只需要一次线性扫描加少量前缀乘积也是O(n)时间代码写起来甚至更短。不过实际面试和考试中DP版是被广泛认可的通用解因为它不需要考虑各种分段细节思维量更低而且遇到0也能自动处理。我的建议是考试写DP稳平时训练可以拿“按0分段”的思路来验证自己对负数规律的理解。4.5 大数溢出问题的提醒最后说一个很多人忽略的细节int型的溢出。数组里的元素可以在[-1000, 1000]级别如果数组很长且正数很多中间过程的乘积很可能超过int的范围。这题的测试数据如果比较温和int勉强够用如果数据比较极限建议直接用long long保存maxF和minF。C里定义成long long maxF nums[0]基本上就能避开溢出问题。Python不涉及这个因为Python的整数可以无限大。我在实际测试中遇到过一组数据[1000, 1000, 1000, 1000, 1000]int版直接溢出为负数导致答案错误。这个坑特别隐蔽因为溢出结果看起来像是一个正常的负数你的程序不会崩但就是WA。所以只要乘积题我第一反应就是开long long这已经是肌肉记忆了。5. 从这道题延伸出去一个思路解决一类题这题做完之后你会发现一个特别有意思的现象动态规划的状态设计不是拍脑袋想出来的而是根据“当前选择会受到哪些历史因素的影响”来确定的。最大子数组和只受“历史最大值”影响所以一个状态够用最大乘积同时受“历史最大值”和“历史最小值”影响所以必须两个状态。把这种思维方式迁移出去你就可以解决一系列“看起来差不多但其实完全不一样”的题目。比如求最大绝对值的连续子数组、求乘积为正数的最长子数组长度、求加减交替的最长子序列……这些题的共性都是状态转移时你不仅要考虑“最优状态”还要考虑“最劣状态”。因为最劣状态在某些条件下会翻转成最优状态。我个人的学习心得是做OJ题不能只看AC了没有你得学会“给自己出题”。比如这题AC了你可以改一改“如果允许跳过而不是丢弃0答案会怎样变化”“如果数组长度达到10的6次方空间复杂度能否从O(1)降到O(1)要不要开数组”这种头脑实验比盲目刷下一题有用得多。最后分享一个小技巧是我刷了上百道DP题之后总结出来的遇到动态规划题先别看题解手工构造五个用例正常用例、全正数、全负数、含0、单个元素在每个用例上把转移过程手推一遍。推不出矛盾说明你的状态设计合理推到一半发现结果不对恭喜你你已经提前发现了隐藏的坑。这道“最大乘积”题只要你能靠手推发现“必须同时维护最大值和最小值”那你的DP基本功就真的过关了。
