企业官网建设流程全解析

那天下午在某个线上练习赛里，我卡在了一道题上，题目名字就叫“统计比赛得分最大”，给你一个长度为 (n) 的数组，表示某场比赛里连续若干轮次的分差，要求找出其中一段连续轮次，使得这段得分总和最大。说白了，就是经典的最大子数组和问题，也叫最大子段和。当时我以为能轻松秒掉，结果因为没注意边界条件，WA了两发才缓过来，所以今天我把这题从暴力到最优解完整拆一遍，顺便把比赛里容易踩的坑也一起列出来。

这个问题解决的事情很简单：给一个数组，找出一个连续子数组，使它的元素之和最大。适合刚开始学算法、准备各类编程比赛、或者正在复习动态规划的读者，也适合想把手写代码的边界处理做扎实的人。不管你是刚接触“最大子数组和”，还是已经能背出 Kadane 算法，我都建议你把这篇从头看一遍，因为我不仅讲原理，还会讲什么时候用哪种写法、为什么这样写不会错，以及各种变体和隐蔽的坑。

1. 问题拆解与思路选择

1.1 题目理解与样例分析

先把题意固定下来：输入一个整数数组，比如[1, -2, 3, 5, -1, 2]，要找到一段连续的子数组，使得这一段里所有数字的和最大。这段子数组至少包含一个元素，不能为空。

我们可以先手动推一遍这个样例：

• 从第 1 个元素开始的所有子数组：[1]、[1, -2]、[1, -2, 3]、[1, -2, 3, 5]……
• 从第 3 个元素开始的子数组：[3]、[3, 5]、[3, 5, -1]、[3, 5, -1, 2]，其中[3, 5, -1, 2]的和是 9。

继续看的话，最大和其实是[3, 5, -1, 2]，总和为 9。但如果是[1, -2, 3, 5, -1, 2]这个数组，从第 3 项到第 6 项就是 3+5-1+2=9。如果数组变成[5, -1, -2, 3]，最大和是 5，还是[5, -1, -2, 3]的 5？做题时如果只凭直觉，很容易漏掉“负数放在中间反而可以连接两段正数”的情况。

所以这道题的核心不是简单地找最大元素，而是要处理子数组的“连续性”。这也是为什么它经常被当作动态规划入门题的原因，因为它的状态转移非常自然。

1.2 暴力枚举为什么不够用

很多人第一反应是枚举起点和终点，也就是两层循环：

int maxSum = INT_MIN; for (int i = 0; i < n; i++) { int sum = 0; for (int j = i; j < n; j++) { sum += a[j]; maxSum = max(maxSum, sum); } }

这种做法很好理解，但时间复杂度是 (O(n^2))。当 (n = 10^5) 时，循环次数是 (10^{10}) 级别，比赛环境里基本属于超时。而且一旦题目加个“输出方案”或者“二维矩阵版本”，暴力枚举就完全没法看了。

除非题目给的 (n) 很小（比如 (n \le 100)），否则不要写 (O(n^2))。我见过有人在正式赛里为了省事直接套两层循环，结果数据范围是 (2 \times 10^5)，白白丢分。正确思路是：先看数据范围，再决定用什么算法，这比背模板重要得多。

2. 核心解法：Kadane 算法的原理与实现

2.1 状态定义与转移方程

让我先把“为什么”讲清楚。假设我们用dp[i]表示以第i个元素结尾的子数组的最大和。那么dp[i]只有两种可能：

• 要么把a[i]接到前面dp[i-1]那个最优子数组的后面；
• 要么就自己单独作为一个新的子数组（因为前面那段和是负数，接了反而更小）。

所以状态转移方程就一句话：

dp[i] = max(a[i], dp[i-1] + a[i])

最终答案是所有dp[i]里的最大值，而不是dp[n-1]。这一点特别容易搞错，因为很多动态规划题最后答案就是dp[n-1]，但这题不是，最大子数组可以在数组的任何位置结束。

我们可以用一个例子来理解：数组[-2, 1, -3, 4, -1, 2, 1, -5, 4]。

可以看到，最大和是 6，对应的子数组是[4, -1, 2, 1]。整个过程里，每次我们只需要知道前一个dp[i-1]，所以可以把一维数组压缩成一个变量，这就是 Kadane 算法的由来。

2.2 从状态转移到 Kadane 算法

把上面的状态转移压缩成两个变量：

int maxSum = a[0]; int curSum = a[0]; for (int i = 1; i < n; i++) { curSum = max(a[i], curSum + a[i]); maxSum = max(maxSum, curSum); }

这里curSum就是当轮的dp[i]，maxSum负责记录历史上出现过的最大值。为什么是max(a[i], curSum + a[i])而不是直接curSum += a[i]？因为如果curSum已经是一个负数，那么把它加到a[i]上只会让结果更小，不如直接从a[i]重新开始一段。

很多文章喜欢讲“贪心”视角：只要当前和大于 0，就继续累加；一旦当前和变成负数，就重置为 0。这也是对的，而且实现更简洁：

int maxSum = INT_MIN; int curSum = 0; for (int i = 0; i < n; i++) { curSum += a[i]; maxSum = max(maxSum, curSum); if (curSum < 0) curSum = 0; }

看起来不太一样，其实两者是等价的。区别只在于重置时机：第一种写法是“先把当前元素算进来，再判断要不要丢”；第二种是“先算，再更新答案，最后如果和为负就丢掉”。我个人更推荐第二种，因为它天然处理了“子数组至少一个元素”的限制，而且当你想扩展成“允许选择空子数组”（即最大和可以为 0）时，只需要把maxSum初始化为 0，并且把if (curSum < 0) curSum = 0;放到更新答案前面，逻辑上更清晰。

2.3 完整代码模板与复杂度分析

这里给出一份用第二种写法整理的完整代码，可以直接用在比赛里：

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; int maxSum = INT_MIN; int curSum = 0; for (int i = 0; i < n; i++) { curSum += a[i]; if (curSum > maxSum) maxSum = curSum; if (curSum < 0) curSum = 0; } cout << maxSum << endl; return 0; }

时间复杂度 (O(n))，空间复杂度 (O(1))（不算存数组本身的话）。在线性扫描的每一轮里，做的都是常数次加减和比较，所以即使 (n = 10^6) 也能轻松跑完。空间上如果不做后续输出方案，甚至可以边读边处理，连数组都不用存，省内存又提速。

还有一个小技巧：maxSum的初始值不要用0，除非题目保证答案可以为 0。否则遇到[-1, -2, -3]这种全负数数组，maxSum就会错误地输出 0。本着最稳妥的原则，我一般用INT_MIN，或者直接初始化为a[0]，然后从下标 1 开始循环。

3. 边界场景与多解法对比

3.1 不同处理方式的适用场景

Kadane 算法不是唯一的解法，某些场景下其他思路也有用。我整理了一张表，方便你根据题目变化选型：

前缀和思路是：先算出prefix[i]表示a[0]到a[i-1]的和，然后区间[l, r]的和就等于prefix[r+1] - prefix[l]。要找到最大子数组和，只需要在遍历r的同时维护最小的prefix[l]。写出来就是：

int prefix = 0; int minPrefix = 0; int maxSum = INT_MIN; for (int i = 0; i < n; i++) { prefix += a[i]; maxSum = max(maxSum, prefix - minPrefix); minPrefix = min(minPrefix, prefix); }

这个方法比 Kadane 算法多一个变量，但优点在于它把“和”拆成了差的形式，遇到“求最大平均子数组”“最大子数组和至少长度为 k”这类变体时，前缀和思路往往更顺手。分治法则是把数组从中间劈开，最大子数组要么完全在左半，要么完全在右半，要么跨过中点。跨过中点的情况需要从中点向两边扩展，分别求左半最大后缀和右半最大前缀，然后加在一起。

3.2 全负数数组的正确结果

有一个经典测试用例是[-2, -1, -3]。错误答案经常是 0，因为有人把curSum重置为 0 后顺手把maxSum也设为 0。正确答案应该是 -1，因为子数组至少包含一个元素，你必须选一个最大的负数。

用我们上面的第二种代码，整个过程是这样的：

• curSum += -2，maxSum = -2，curSum < 0，重置为 0；
• curSum += -1，maxSum = max(-2, -1) = -1，curSum < 0，重置为 0；
• curSum += -3，maxSum = max(-1, -3) = -1，curSum < 0，重置为 0。

最终输出-1，正确。如果你把初始maxSum设为 0，那结果就是 0，直接 WA。所以我的习惯是：只要题目没说“可以为空”，一律用INT_MIN初始化。

有些题目会明说“你可以选择一个空子数组，此时和为 0”，比如某些金融场景的建模题，这时候答案就应该是 0，而不是最大的负数。遇到这种题，只需要把maxSum初始化为 0，并调整先更新答案还是先重置的顺序即可，其他都不用动。

3.3 变体一：输出最大子数组本身

很多比赛题不只让你输出最大和，还要你输出对应的起点和终点。这时候 Kadane 算法需要记录“上一次重置的位置”。做法也很简单：每当我们选择从a[i]重新开始时，就把当前起点记下来；每当curSum更新了maxSum，就同步更新最终起点和终点。

int maxSum = INT_MIN, curSum = 0; int start = 0, end = 0, tempStart = 0; for (int i = 0; i < n; i++) { if (curSum < 0) { curSum = 0; tempStart = i; } curSum += a[i]; if (curSum > maxSum) { maxSum = curSum; start = tempStart; end = i; } }

注意一个细节：重置的时机要在累加之前。我最初写的时候把if (curSum < 0) curSum = 0;放在curSum += a[i]之后，结果起点总是错过一位。你仔细想想，tempStart = i的意思是“从当前这个位置重新开始”，所以必须先判断前一段是否已经变负，再决定起点位置，最后累加当前值。这个顺序错一步，输出的子数组就偏了。

3.4 变体二：二维矩阵最大子矩阵

如果把数组扩展成矩阵，让你找出一块子矩阵使元素和最大，怎么办？常见做法是枚举上下边界，把每一列的值压成一个一维数组，然后对这个一维数组跑 Kadane 算法。也就是说，把二维问题降维成一维问题，本质还是最大子数组和。

伪代码大概是：

int maxSum = INT_MIN; for (int top = 0; top < rows; top++) { vector<int> colSum(cols, 0); for (int bottom = top; bottom < rows; bottom++) { for (int j = 0; j < cols; j++) colSum[j] += matrix[bottom][j]; int cur = 0; for (int j = 0; j < cols; j++) { cur = max(colSum[j], cur + colSum[j]); maxSum = max(maxSum, cur); } } }

这个做法的关键在于：枚举上下边界需要 (O(m^2))，每一层往内部累加列和是 (O(m \cdot n))，最后整体是 (O(m^2 n))。如果矩阵是方阵，就是 (O(n^3))。对于 (n \le 200) 的数据，这个复杂度是可以接受的；如果 (n) 到了 1000，就需要考虑更复杂的优化了。

我在刷题时遇到过一个二维版本的题，当时慌了，因为一维的 Kadane 很熟，二维却不知道怎么下手。其实只要记住“降维”这个思路，先枚举上下边界，再把列和压成一维，后面的流程就和一维完全一样了。这类题考察的就是你能不能把新问题映射到旧模型上，所以别再背二维模板，理解降维原理更重要。

4. 比赛现场常见错误与排查经验

4.1 三个最容易踩的坑

第一个坑：初始化值搞错。maxSum = 0导致全负数数组 WA，这个前面说过了，不再赘述。

第二个坑：curSum重置时机不对。 有时候你写的是：

curSum = max(0, curSum + a[i]); maxSum = max(maxSum, curSum);

这个写法在“空子数组合法”时是对的，但在“至少选一个元素”时是错的。因为如果a[i]是负数且curSum + a[i] < 0，curSum会被强行置为 0，然后maxSum可能永远更新不了最大的负数。必须保证maxSum至少能取到数组里最大的那个负数，办法就是先累加、再更新答案、最后重置，顺序不能乱。

第三个坑：数组里有大负数，导致中间结果溢出。 如果数字范围是[-10^9, 10^9]，长度是10^5，那么最大和可能到10^14，超过 32 位 int 的范围。这时候必须开long long。我见过某位同学在比赛里用 int 存curSum，结果样例全过，提交后 WA 一片，排查了半天才发现是溢出。所以做题第一步先看数据范围，sum类变量直接用long long是最稳的选择，哪怕是小题，多花一点内存换安心值得。

4.2 如何快速定位逻辑错误

如果你提交后 WA，不要急着看大数据，先从这几个方向查：

• 构造全负数用例，比如[-1, -2, -3]，看输出是不是 -1；
• 构造交替正负用例，比如[1, -1, 1, -1, 1]，看输出是不是 2；
• 构造单一元素用例，比如[7]，看输出是不是 7；
• 构造首尾为负的用例，比如[-5, 4, 3, -6]，看输出是不是 7。

这些用例都不长，手动都能跑出结果，但如果能写成小测试函数批量跑，排查速度会快很多。我一般会在本地把 Kadane 算法和一个暴力 (O(n^2)) 版本放在一起，随机生成数组，对拍几百组数据。只要两边结果不一致，就把用例打出来，然后缩小范围看是哪一步状态转移出了偏差。这种做法只花五分钟，省下的是赛后半小时的懊恼。

因为手写 Kadane 本身代码量很少，如果真的 WA，大概率不是逻辑设计问题，而是边界初始化的问题。我强烈建议你养成用INT_MIN/LLONG_MIN初始化答案变量的习惯，同时检查数组下标是否可能为负，是否需要从 0 还是 1 开始读入。

4.3 复杂场景下如何选择算法

有些题表面是“最大子数组和”，实际还夹带了别的限制，比如：

• 子数组长度必须至少为 k；
• 允许你删掉最多一个元素后再求最大子数组和；
• 数组是环形的，首尾相连；
• 需要返回最大和的同时还要返回方案数量。

这些变体里，有的能靠改 Kadane 解决，有的要换思路。比如“环形数组的最大子数组和”，通常做法是：结果要么是数组内部的常规最大子数组，要么是跨越首尾的子数组，而跨越首尾的情况等价于数组总和减去内部最小子数组和。所以你就需要同时维护最大子数组和maxSum和最小子数组和minSum，最后答案是max(maxSum, totalSum - minSum)。当然，要小心全部为负数的情况，此时常规maxSum已经是正确答案。

再比如“至少长度为 k 的最大子数组和”，直接 Kadane 就不太合适了，因为你必须保证子数组长度不低于 k。这时候用前缀和 + 滑动窗口维护最小前缀和是更清晰的思路：先算出前缀和数组prefix，然后从i = k开始遍历，记录前i - k个前缀里的最小值，用prefix[i] - min(prefix[0..i-k])更新答案。很多人想不到这一步，因为 Kadane 算法太顺手了，反而忽略了前缀和对“长度限制”这类条件的天然适配。

所以我的建议是：Kadane 算法要滚瓜烂熟，前缀和也要理解透彻，两者配合使用，覆盖面才够广。真正比赛的时候，多花十秒想想这道题有没有隐藏限制，比急着抄模板要靠谱得多。

4.4 关于对拍和随机数据

对拍这个技巧值得单独说。写代码是一回事，验证代码是另一回事。我平时写这种微小算法的题，都会顺手写一个暴力函数作为“参考实现”，然后生成随机小数据，把两个函数的结果做对比。伪代码长这样：

int brute(vector<int>& a) { int n = a.size(); int ans = INT_MIN; for (int i = 0; i < n; i++) { int sum = 0; for (int j = i; j < n; j++) { sum += a[j]; ans = max(ans, sum); } } return ans; } int kadane(vector<int>& a) { int ans = INT_MIN, cur = 0; for (int x : a) { cur += x; ans = max(ans, cur); if (cur < 0) cur = 0; } return ans; }

然后循环 10000 次，每次生成n在 1 到 20 之间的随机数组，元素范围在 -50 到 50 之间，比较brute和kadane的输出。如果全部一致，代码基本是稳的。这样做尤其适合初学阶段，能帮你建立“边界感”，以后再遇到类似题，心里就有底了。

5. 从这一题延伸出去的思维模型

5.1 为什么“最大子数组和”这么重要

这个题在面试和比赛里出场率极高，不是因为它难，而是它恰好踩在一个关键转折点上：从“线性枚举思维”跳到“状态压缩思维”。你会从这个题里同时体会到三样东西：

• 动态规划的状态定义到底该怎么设计；
• 如何利用贪心/剪枝思想去掉无用状态；
• 如何把二维甚至多维问题降维成熟悉的一维模型。

尤其是第一点，很多初学者学动态规划是从背包开始的，但背包的状态转移相对抽象，反而不如最大子数组和这么直观。这个题的dp[i]定义清晰，转移只有两条分支，答案还要遍历取最大，是非常好的入门教材。

我在准备比赛的那段时间，常常会把一个经典题目吃透，再把它往各个变体上套。最大子数组和就是非常适合做“母题”的题目。你在纸上把它的转移方程推一遍，再看几道变体题，很多难度更高的动态规划题就会变得没那么神秘。

5.2 比赛得分统计的另一个视角

标题里提到“统计比赛得分最大”，其实很多真实赛题会把这个场景包装成“每轮得分的净胜分”“连续命中的时刻”“一段时间内的最大收益”等。它们的核心永远是一个数组，你要找出连续的、加和最大的一段。

有一次模拟赛里，题目把数组换成了每天的盈利和亏损，让你求“最长连续盈利周期”的最大净利润。这不就是最大子数组和吗？但当场有人为了找“最长周期”去维护长度，导致算法复杂度飙升。实际上，只要先求出每个位置结尾的最大子数组和以及对应长度，再在全局最大时顺便比较长度，就能同时解决。所以，面对任何包装后的题目，先识别出底层的数组模型和求和逻辑，比死记硬背任何模板都重要。

5.3 从最大子数组和到更多动态规划题

如果你已经能轻松默写 Kadane 算法，可以继续试试这几道进阶题，权当练手：

• 乘积最大子数组（注意正负号，需要同时维护最大值和最小值）；
• 最佳观光组合（把a[i] + i和a[j] - j拆开维护）；
• 接雨水（本质是左右最大值的结合，也能用动规预处理）；
• 连续子数组的最大和（带取模或限制长度的变体）。

你会慢慢发现，它们都在用同一个思维工具：把“以某个位置结尾”的子问题定义出来，再看这个子问题能不能用之前的状态 O(1) 转移。一旦掌握了这层，就不仅仅是会了一道题，而是掌握了一类题的解题范式。

我个人在实际练习中的体会是：这道题真正值钱的不是那几行代码，而是你愿意花多少时间在它身上“抠边界”。把全负数、单元素、交替正负、数据溢出这些情况全部手动跑通一遍，比做十道类似的新题更有价值。做题速度快的选手，不是因为他们见过的题多，而是因为他们能在看到题的第一眼就完成“问题归约”，而这依赖的就是平时对这些基础模型的反复打磨。

最后再分享一个小技巧：如果你在比赛中遇到“输出最大和的子数组”这类要求，记得把tempStart和start分开存，不要想着用同一个变量既记录当前候选起点又记录最终起点。你对curSum做重置的时候，tempStart会跟着变；只有更新maxSum的时候，start才应该变化。这个细节我吃亏过两次，写出来给你做个提醒。