刷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 Error（PE）。
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。但题目要的就是这个边界判断，不做就会在某个测试点上WA（Wrong Answer）到怀疑人生。
1.3 数据范围决定算法方向
东华OJ这道经典题很老，n的数据范围一般是n <= 18，每个数字取值范围是-10到10。为什么要强调数据范围？因为：
- n只有18，总子段数量是
n*(n+1)/2 = 171个，暴力枚举完全可行。 - 每个数字绝对值最大是10，18个10相乘就是
10^18，这个值刚好卡在long long的范围附近（9.22*10^18），所以可以用64位整数存结果。 - 正因为n小，所以题目其实并没有强求你用动态规划，你暴力枚举也能过。
但作为一篇正经的经验分享，我建议你暴力解法一定要会，同时也要把动态规划的思路搞明白。因为n一旦放大到10^5，暴力就原地爆炸，那时候就必须上DP了。刷题最忌讳的就是只背一种解法，换个数据范围就废了。
2. 暴力枚举法——先把问题想透，再谈优化
2.1 两层循环枚举所有连续子段
最直观的思路是什么？把每个可能的连续子段都乘一遍，记录最大值。连续子段由起点i和终点j决定，只要枚举i从0到n-1，j从i到n-1，然后把这之间的所有数乘起来就行。
很多初学者会在这里犯一个经典错误：用三层循环，先枚举起点，再枚举终点，再用一层循环计算起点到终点的乘积。三层循环算下来是O(n^3)，虽然n=18时也能跑，但代码很冗余，而且完全没有必要。
其实可以在枚举终点时逐步累乘。也就是说，固定起点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) { vector<int> 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 暴力法的局限
n=18时暴力法当然没问题，但你要把这个思路平移到LeetCode 152题（最大乘积子数组），数据范围是10^5，O(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. 完整代码与心法——从题目到手撕AC
4.1 动态规划最终代码
#include <bits/stdc++.h> using namespace std; int main() { int n; while (cin >> n) { vector<int> 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
前面说过，n=18，每个数最大能到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 long |
| PE格式错误 | 多了或少了换行/空格 | 看清输出格式要求 |
| RE运行时错误 | 数组越界 | 检查 n=1 时的特殊情况 |
| 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]，手动推一遍：
- i=0：curMax=-1，curMin=-1，ans=-1
- i=1：tmpMax=-1，tmpMin=-1
- curMax = max(-1, 1, 1) = 1
- curMin = min(-1, 1, 1) = -1?
等等，这里tmpMin * a[1]是(-1)*(-1)=1，不是1吗？min(-1, 1, 1)得到-1。然后ans更新为1。输出1，符合预期。
这个手动推导过程特别值得自己走一遍。很多人在纸上推一遍，自己对状态转移的理解就会上一个台阶。
5.4 常见的OJ报错判读
第一次提交时如果返回了 Compile Error（CE），别急着摔键盘。先看错误信息，东华OJ会返回编译器的提示。大部分CE都是因为头文件写错、变量名冲突、或者忘了C++版本。
Running Time Error（RE）的话，优先怀疑数组越界。n很小的时候也有可能出现，比如你定义数组为a[n]但访问了a[n]这个不存在的下标。C++数组下标从0开始，最后一个是a[n-1]。
Time Limit Exceeded（TLE）基本不用太担心，n=18暴力都能过，何况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世界的游戏规则。
