中–难 · 一趟遍历一个念头
最大子段和
数组里所有连续的一段中,哪一段的和最大?暴力解法是 O(n²)。而那个关键的洞察只有一句话。
一句话答案Kadane 算法 —— running = max(a[i], running + a[i])，best = max(best, running)；因为要求区间非空，全负数的数组也算得对。
题目
输入: 第一行一个整数 n(1 ≤ n ≤ 1000)。第二行 n 个空格隔开的整数(−1000 ≤ ai ≤ 1000)。可能有负数。
输出: 非空连续子段可能达到的最大和。
样例:
| 输入 | 输出 |
|---|---|
8 | 6 |
5 | -1 |
1 | 5 |
第一个样例里最好的一段是 4 -1 2 1 = 6。第二个样例全是负数,但你仍然必须选一段 —— 答案是 −1,不是 0。大多数解法就挂在这里。
你的解答
「运行我的输入」用的自定义输入
判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。
卡住了？提示
提示 1 — 先看暴力解法,体会它有多浪费
枚举每个起点 i、每个终点 j,求和取最大。这是 O(n²) —— n = 1000 时大约一百万次加法,而且大部分都在重复计算你已经算过的和。快解法从不回头看。
提示 2 — 一个「当前累计」就够了
维护 cur = 以当前位置结尾的最优子段和。下一个数 x 到来时,你只有两个选择:接上(cur + x),或者在 x 处重新开始。取较大的那个。然后如果 cur 超过了 best 就更新 best。
提示 3 — 那一句话的洞察
如果 cur 是负的,它只会把下一个数往下拖 —— 扔掉它,重新开始。就这一句:if (cur < 0) cur = x; else cur = cur + x;。其余都是记账。
题解（先自己试试！）
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int best, cur;
cin >> best;
cur = best;
for (int i = 1; i < n; i++) {
int x;
cin >> x;
if (cur < 0) cur = x;
else cur = cur + x;
if (cur > best) best = cur;
}
cout << best << endl;
return 0;
}这是 Kadane 算法,也是动态规划的标准入门:cur 是一个状态,它用一个数概括了你需要知道的全部过去。你并没有记住数组 —— 你只记住了唯一重要的那件事。这种重新表述 ——「我必须往前带的最小信息是什么」—— 就是这门手艺的全部。它也是闯关链的最后一题:你已经走过了输入输出、循环、数组、字符串、位运算、排序、查找和一个真正的算法。回头看看题库列表,数数有多少道你能不看提示做出来。
深度解析
为什么这样做对
维护 cur = 以当前位置结尾的最优子段和。下一个数到来时你只有两个选择:接上,或者从它重新开始。取大的那个。
代价
O(n) 一趟,只多两个变量。枚举所有区间是 O(n²) —— 而且其中大部分加法都在重复计算已有的和。
常见错法
- 把
best初始化成 0:全是负数时输出 0,但空子段是不允许的,正确答案是最大的那个负数。 - 用
if (x > 0)而不是if (cur < 0)决定接不接 —— 这会硬接上一段本该扔掉的负累计,最大和就偏小了。
下一步
闯关到这里结束。回头看看 第一题 —— 你已经走了很远。
记住这两句
- 负的累计只会拖累你 —— 扔掉它,从当前这个数重新开始。
- 动态规划的核心问题:我必须往前带的最小信息是什么?
🐞 这段是错的 —— 点开,亲手让它挂一次
best 从 0 开始 —— 全是负数时输出 0,但空子段是不允许的
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int best = 0, cur = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (cur < 0) cur = x;
else cur = cur + x;
if (cur > best) best = cur;
}
cout << best << endl;
return 0;
}