刷OJ的时候碰到东华大学OJ的第39题“最大乘积”这道题卡了我一会儿做出来之后回头想了想觉得里面有很多值得展开聊聊的东西。不光是这道题的解法本身还包括怎么在OJ上用正确的方式读题、分析数据范围、选算法以及提交之后怎么根据报错调代码。这篇文章就用这道题作为例子把从读题到AC的完整链路捋一遍。先说结论这道题表面上只是一个“求最大连乘子段”的经典问题但它在数据范围、边界条件、输出格式上埋了好几个雷。你要是能把这道题彻底吃透OJ系统常见的那几类坑多组输入、特殊值输出、溢出、全负数场景基本就都有体感了对后面刷动态规划、贪心这些专题会有很大帮助。1. 先把题目彻底读懂再说怎么写代码1.1 输入输出到底长什么样东华OJ的很多题目都是多组测试数据。这道题也不例外。输入一般长这样3 1 2 3 2 -1 -1 3 -1 0 -2第一行是n代表序列长度第二行给n个整数。然后可能会继续给下一组一直到文件结束。很多新手第一次接触多组输入会直接懵我只处理一组行不行不行OJ评测会把所有测试点跑一遍你的程序必须能读完全部输入。输出也比想象中要严格。每一组结果单独占一行大部分OJ还要求“每组输出之后跟一个空行”或者“Case #x: ”之类的格式。东华这题如果题干没额外要求直接输出结果换行即可但你要是习惯了LeetCode那种只需要返回结果值的模式第一次做题往往会踩到输出格式不对导致的Presentation ErrorPE。1.2 题目里最容易看漏的隐藏条件我特意去翻了这道题的原题描述核心要求是给定一个整数序列找到乘积最大的连续子序列输出这个最大乘积。如果最大乘积不是正数输出 -1。这里有几个关键信息“连续子序列”意味着你不能排序不能重新排列只能在原始顺序里切一段。整数序列里有负数也有可能有0。最大乘积如果不是正数就输出 -1。第三条是很多人会忽略的重点。比如序列是[-1, -2]连续子序列乘积最大其实是(-1)*(-2)2它是正数所以输出2这个没问题。但如果序列是[0, -2, -3]呢0是最大的吗不是(-2)*(-3)6。那如果序列是[-1, 0, -2]呢所有连续子序列乘积分别是 -1、0、-2、0、0、2最大的是2。但如果序列是[-1, -2, 0]呢最大子段是(-1)*(-2)2不是0。真正会走到输出 -1 的场景是类似于[0, -1, -2]这样等等0包含在[0,-1,-2]整体里是0但(-1)*(-2)又是2。所以大家看负数只要凑成偶数个数乘积就会变正。真正的“最大乘积不是正数”的情况是序列中任意连续段乘出来都不可能为正比如[-1, -2, -3]这里(-2)*(-3)6又是正的。大家发现规律了吗只要序列中存在两个以上的负数并且它们之间不隔着0那么乘积就可以是正数。所以真正会输出-1的情况其实很少基本是序列全为0或者只有一个负数且其余为0或者全是0。但题目要的就是这个边界判断不做就会在某个测试点上WAWrong Answer到怀疑人生。1.3 数据范围决定算法方向东华OJ这道经典题很老n的数据范围一般是n 18每个数字取值范围是-10到10。为什么要强调数据范围因为n只有18总子段数量是n*(n1)/2 171个暴力枚举完全可行。每个数字绝对值最大是1018个10相乘就是10^18这个值刚好卡在long long的范围附近9.22*10^18所以可以用64位整数存结果。正因为n小所以题目其实并没有强求你用动态规划你暴力枚举也能过。但作为一篇正经的经验分享我建议你暴力解法一定要会同时也要把动态规划的思路搞明白。因为n一旦放大到10^5暴力就原地爆炸那时候就必须上DP了。刷题最忌讳的就是只背一种解法换个数据范围就废了。2. 暴力枚举法——先把问题想透再谈优化2.1 两层循环枚举所有连续子段最直观的思路是什么把每个可能的连续子段都乘一遍记录最大值。连续子段由起点i和终点j决定只要枚举i从0到n-1j从i到n-1然后把这之间的所有数乘起来就行。很多初学者会在这里犯一个经典错误用三层循环先枚举起点再枚举终点再用一层循环计算起点到终点的乘积。三层循环算下来是O(n^3)虽然n18时也能跑但代码很冗余而且完全没有必要。其实可以在枚举终点时逐步累乘。也就是说固定起点i然后让j从i开始往右走同时用一个变量mul累乘a[j]每走一步就更新一次最大值。这样只需要两层循环复杂度是O(n^2)。2.2 关键代码与原理解读#include bits/stdc.h using namespace std; int main() { int n; while (cin n) { vectorint a(n); for (int i 0; i n; i) cin a[i]; long long maxProd 0; // 注意初值题目要求非正数输出-1 bool hasPositive false; for (int i 0; i n; i) { long long cur 1; for (int j i; j n; j) { cur * a[j]; if (cur maxProd) { maxProd cur; } } } if (maxProd 0) cout -1 endl; else cout maxProd endl; } return 0; }这个代码有个很巧的地方cur在固定起点的情况下每乘一个数就更新一次天然就覆盖了所有“同一个起点、不同终点”的子段。两层循环搞定不需要额外的“计算乘积”循环。但这里我要特别提醒一个初值问题maxProd我设成了0而不是无穷小。为什么敢设0因为题目说了“如果最大乘积不是正数输出-1”。也就是说如果你最后算出来的maxProd是0或者负数就直接输出-1。设成0就相当于把“正数”作为初始基准跑完循环只要maxProd还是0说明压根没找到正数乘积直接输出-1就行。而如果你是设成INT_MIN后面还得再多写一个判断反而容易漏。2.3 暴力法的局限n18时暴力法当然没问题但你要把这个思路平移到LeetCode 152题最大乘积子数组数据范围是10^5O(n^2)就是妥妥的超时。所以这里就引出一个问题能不能用更聪明的方法一遍遍历就算出最大值能这就是动态规划。3. 动态规划的优化思路——为什么维护最小值很关键3.1 状态设计同时维护最大最小动态规划处理连续子段问题时最经典的套路是用“以i结尾的子数组”作为状态。假设dpMax[i]表示以第i个数字结尾的所有连续子序列中乘积最大的那个dpMin[i]表示乘积最小的那个。为什么要同时维护最小值因为在乘法里一个负数乘以一个负数会变成正数而且这个正数可能比当前最大值还大。如果你只记录最大值碰到负数时就会漏掉“负数乘以之前的最小负数”这种情况。用生活化的类比解释一下你手里有一笔“最大财富”和一笔“最大负债”。有一天你获得了一个翻转机会乘以一个负数最大负债被翻转成了最大财富而原来的最大财富反而变成了负债。所以你两个都得记着机会来了才知道用哪个去翻。3.2 状态转移方程dpMax[i] 的来源有三种可能从nums[i]重新开始一段子序列也就是不接前面的。让nums[i]乘以dpMax[i-1]。让nums[i]乘以dpMin[i-1]。为什么会有第3种因为如果nums[i]是负数而dpMin[i-1]是负数负负得正。同理dpMin[i] 也要从这三种里取最小。写成公式就是dpMax[i] max(nums[i], dpMax[i-1]*nums[i], dpMin[i-1]*nums[i]) dpMin[i] min(nums[i], dpMax[i-1]*nums[i], dpMin[i-1]*nums[i])最终答案就是所有dpMax[i]中的最大值。3.3 滚动数组节省空间dpMax[i]只用到了dpMax[i-1]所以完全不需要开数组用两个变量滚动更新就行。每读入一个数就更新当前的curMax和curMin然后拿curMax去更新全局最大。有两点必须注意更新顺序很关键。如果你先更新了 curMax再用更新后的 curMax 去算 curMin那就错了。因为curMin需要的是“上一轮”的 curMax而不是更新后的。所以要么用临时变量先存旧值要么把两个更新放到同一个公式里交错进行。如果题目改成n范围很大但数字也有0那么遇到0时乘积全部归零dpMax和dpMin都会变成0这也是符合常识的因为以0结尾的子段最大乘积就是0。4. 完整代码与心法——从题目到手撕AC4.1 动态规划最终代码#include bits/stdc.h using namespace std; int main() { int n; while (cin n) { vectorint a(n); for (int i 0; i n; i) cin a[i]; long long curMax a[0], curMin a[0]; long long ans a[0]; for (int i 1; i n; i) { long long tmpMax curMax; long long tmpMin curMin; curMax max((long long)a[i], max(tmpMax * a[i], tmpMin * a[i])); curMin min((long long)a[i], min(tmpMax * a[i], tmpMin * a[i])); ans max(ans, curMax); } if (ans 0) cout -1 endl; else cout ans endl; } return 0; }这段代码比暴力法多了一点点思考门槛但扩展性很强。你把n改成一百万也照样跑得动时间复杂度只有O(n)。4.2 为什么用long long而不是int前面说过n18每个数最大能到10那么18个10相乘是10^18。这个数已经超过int的范围了int最大约2.1*10^9所以一旦遇到全10的测试数据用int存储乘积会直接溢出WA得莫名其妙。这种题用long long是基本操作但就是有很多人会忽视。其实我在实际比赛里也踩过这个坑。记得有次做一道“最大子序列乘积变种题”我自信满满用int写完提交之后WA了三次最后才意识到10个100相乘就爆int了换成long long立刻AC。从那之后凡是涉及乘法的题我都会下意识地用64位整数。4.3 关于多组输入的处理东华OJ很多题目都是“输入包含多组测试数据每组占两行”。代码里用的while (cin n)就是典型写法。它的原理是cin n在成功读取到数据时返回非0值读到EOF文件结束符时返回0循环停止。新手容易出问题的地方在于处理完一组之后忘了重置变量。比如暴力法中那个maxProd如果把它定义在循环外面第二组测试数据就会带着上一组的残留值结果全乱套。我自己一般会习惯性把所有变量都定义在while循环内部这样每组数据都是全新的状态。另外如果输出要求每组之间有空行你得注意最后一个输出后面不能有多余空行否则会PE。东华这题我印象中没这个要求但如果有可以在每组后面直接输出一个空行题目的special judge一般会忽略最后多余的空格和空行但保险起见还是按严格格式来。5. 常见问题与排查技巧实录5.1 易错点速查表易错场景原因排查方法WA但样例能过漏了多组数据中的状态重置检查变量是否定义在循环外WA且答案很大int溢出换成long longPE格式错误多了或少了换行/空格看清输出格式要求RE运行时错误数组越界检查 n1 时的特殊情况WA在某些负数和0的数据上没有处理“非正数输出-1”用全负数测试用例自测5.2 自测用例与陷阱验证我最推荐的做法是写完代码后自己构造几组边界数据来测而不是只依赖样例。下面这组用例非常经典4 0 0 0 0所有连续子序列乘积都是0最大乘积不是正数输出-1。很多初学代码能算出0但忘了转成-1。再来一组2 -1 -1最大子段是(-1)*(-1)1输出1不能因为看到负数就输出-1。再来一组1 -5唯一的连续子序列就是它自己乘积是-5非正数输出-1。5.3 为什么我的动态规划输出不对如果你用上面的动态规划代码去测[-1, -1]手动推一遍i0curMax-1curMin-1ans-1i1tmpMax-1tmpMin-1curMax max(-1, 1, 1) 1curMin min(-1, 1, 1) -1?等等这里tmpMin * a[1]是(-1)*(-1)1不是1吗min(-1, 1, 1)得到-1。然后ans更新为1。输出1符合预期。这个手动推导过程特别值得自己走一遍。很多人在纸上推一遍自己对状态转移的理解就会上一个台阶。5.4 常见的OJ报错判读第一次提交时如果返回了 Compile ErrorCE别急着摔键盘。先看错误信息东华OJ会返回编译器的提示。大部分CE都是因为头文件写错、变量名冲突、或者忘了C版本。Running Time ErrorRE的话优先怀疑数组越界。n很小的时候也有可能出现比如你定义数组为a[n]但访问了a[n]这个不存在的下标。C数组下标从0开始最后一个是a[n-1]。Time Limit ExceededTLE基本不用太担心n18暴力都能过何况O(n)的DP。真超时就检查一下是不是死循环比如某个while循环忘了更新变量或者EOF判断写错了。6. 这道题还能怎么延伸6.1 和力扣152的对比LeetCode第152题“乘积最大子数组”和东华这题是孪生题区别在于LeetCode的返回值直接是最大乘积不用特判“非正数输出-1”而且数据范围更大。如果你把这篇的动态规划代码稍作修改去掉最后的if判断就能直接提交到LeetCode。这种“改改边界就能通吃多平台”的题型非常适合用来练习一题多解和一解多题的能力。我刷题时特别喜欢对同类型题目做横向对比。6.2 如果题目改成求最大非空子序列乘积还有一个非常隐蔽的变种子序列不一定连续但同样要保证相对顺序。此时解法会变得很不一样可能要统计负数的个数、0的位置然后分类讨论。这就从“动态规划”变成了“贪心分类讨论”。有兴趣的话可以想想如果序列里有偶数个负数整个序列乘起来就是正的如果有奇数个负数就得舍弃一个负数具体舍弃哪一个需要比较两端的值。这也是LeetCode上另一道题的思路留给大家自己去思考。6.3 在竞赛中的实战定位在竞赛里这种题一般是送分题位置。但它的意义不在于题目本身多难而在于帮你建立几个肌肉记忆看到“乘积”立刻想溢出问题看到“负数”立刻想负负得正看到“连续子段”立刻想枚举或DP看到“多组输入”立刻想EOF处理。这些肌肉记忆一旦建立后面刷其他DP题、贪心题、模拟题时都会吃香很多。我个人觉得做题刷的不是数量而是这种题感。所谓题感就是看到题目描述第一眼就能预判出这道题的坑点和算法方向。这道“最大乘积”就是训练题感的好素材。说到底OJ系统就像一个严格的教练它不会告诉你哪里错了只会给你一个冷冰冰的WA。你能做的就是自己不断构造测试用例、反复审视代码逻辑、琢磨每一个边界条件。等你亲手把这道“最大乘积”从读题到AC完整走一遍你就真正入门了OJ世界的游戏规则。