解法与C++实战)
最近在帮一批准备 GESP C五级的孩子复盘算法题洛谷 P1115 最大子段和被问到的频率非常高。题目本身很“短平快”给一个长度为 n 的整数序列找出连续且非空的一段使它的和最大。但就是这道看起来简单的题能把贪心思想、时间复杂度优化、边界处理、甚至一题多解串起来。很多人第一次写这道题第一反应是枚举所有区间一提交就是 TLE然后去看题解背了一个“负数就清零”的写法却不理解为什么对。这篇文章我就从最暴力的思路开始推一步步推到 O(n) 的贪心解法再把全负数、溢出、变体和备考 GESP 五级的方法一起讲透。1. 这道题到底在考什么先看懂最大子段和1.1 从洛谷 P1115 的题面说起题面非常简短。第一行是一个正整数 n表示序列长度第二行是 n 个整数可能有正数、负数或零。要求在这 n 个数里找出一段连续的数字这段数字必须非空且所有元素之和最大输出这个最大值。举个例子n7序列是1 -3 4 -1 2 1 -5肉眼扫过去能找到的最大连续子段是4 -1 2 1加起来等于 6。这里是输出 6。注意题目说的是“连续且非空”这意味着你不能跳着选也不能一个都不选。如果序列全是负数你仍必须选一段长度为 1 的子段也就是选一个绝对值损失最小的负数。这种题目叫“最大子段和”也叫“最大连续子序列和”。它在算法题里属于基础中的基础但衍生题非常多比如最大子矩阵、环形数组最大子段和、带长度限制的最大子段和都建立在这道题的理解之上。1.2 数据范围先压死一半人的枚举思路洛谷 P1115 的 n 可以到 200000。这个数据范围意味着什么如果枚举所有区间区间数量大约是 n * (n1) / 2也就是大约 200 亿个肯定超时。就算用前缀和把区间求和优化到 O(1)枚举起点和终点仍然是 O(n^2)对 20 万的数据来说完全跑不动。很多人一开始写代码习惯用两层循环枚举区间左右端点甚至三层循环把中间元素再加一遍。这种思路在 n100 时没问题一旦到了 OJ 上的大数据直接 TLE。所以我一直跟学 C 的孩子说看完题目先别急着写代码先看数据范围心里得先有一个复杂度预算。n200000 的情况下O(n) 或 O(n log n) 是必须的O(n^2) 可以直接不用想。另外这题 a_i 的绝对值可以到 10^4n 最大 200000理论上最大总和能到 2×10^9已经贴近 int 的上限。所以代码里最好直接用 long long避免溢出把自己卡死。1.3 为什么它被归入“贪心思想”考点GESP 五级开始重点引入算法设计思想贪心是其中一个高频考点。最大子段和之所以常被拿来当贪心思想的例题是因为它藏着一个非常经典的“局部最优决策”从左往右累加一旦当前累加和变成负数就果断把它丢弃从下一个位置重新开始。这个决策看起来很“贪心”我不管后面有什么先把当前这一小段的利益最大化如果当前这段不仅没帮我赚钱还在拖后腿那就丢掉。最后再在所有“以某个位置结尾”的最大值里取一个最大的。严格来说Kadane 算法也经常被归为动态规划因为它对应一个状态转移方程。但这道题在不少教学材料和题目标签里都写“贪心思想”因为从理解方式上它确实是最容易讲清楚的贪心入门模型。2. 排除暴力从 O(n^3) 到 O(n^2) 的推演2.1 最直观的三重循环先看最直白的暴力写法#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint a(n 1); for (int i 1; i n; i) cin a[i]; long long ans LLONG_MIN; for (int i 1; i n; i) { for (int j i; j n; j) { long long sum 0; for (int k i; k j; k) sum a[k]; ans max(ans, sum); } } cout ans endl; return 0; }这段代码的思路是枚举左端点 i 和右端点 j然后再用一个 k 循环把区间 [i, j] 里的数全加起来。三层循环的复杂度是 O(n^3)。n200000 时这个复杂度几乎是天文数字运行时间不是几秒的问题而是几百年都跑不完。所以三重循环的唯一意义是帮自己理解题意绝对不能拿去提交。2.2 前缀和优化枚举起点和终点稍微聪明一点的做法是提前算好前缀和这样求任意区间的和只需要 O(1) 时间#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorlong long pref(n 1, 0); for (int i 1; i n; i) { long long x; cin x; pref[i] pref[i - 1] x; } long long ans LLONG_MIN; for (int i 1; i n; i) { for (int j i; j n; j) { long long sum pref[j] - pref[i - 1]; ans max(ans, sum); } } cout ans endl; return 0; }有了前缀和求[i, j]的和只需要pref[j] - pref[i-1]。但这里仍然是两层循环枚举所有区间复杂度 O(n^2)。二十万的数据量平方复杂度就是 400 亿次操作照样超时。不过这一版的价值不是能 AC而是让我们发现一个事实当我们固定右端点 j要算以 j 结尾的最大子段和本质是在问“左端点 i 在 1..j 之间哪个pref[i-1]最小”。因为pref[j] - pref[i-1]要最大减数pref[i-1]就要最小。这其实已经离贪心解法很近了。2.3 这轮推导给了我们什么提示从 O(n^3) 到 O(n^2)问题出在重复计算。我们明明可以一边读入一边处理却非要先把所有区间都枚举一遍。真正的高效解法应该避免枚举而是维护“以当前位置结尾的最大子段和”。这个思路一旦想通O(n) 就顺理成章了。我常在视频里跟学生讲复杂度的优化本质上是在消除无效劳动。三重循环枚举区间的无效劳动在于很多区间的和已经被反复计算过两重循环的无效劳动在于即使求和已经是 O(1)区间数量本身仍然太多。那么能不能不枚举右端点以外的所有左端点答案是可以的这就是贪心/动态规划解法。我们要在“读入一个数、更新一次答案”的过程中把最大子段和直接算出来。3. 贪心核心当前缀和为负数时果断抛弃3.1 从一次手算加深直觉先不写公式我们手算一遍上面的例子1 -3 4 -1 2 1 -5。从第一个数开始当前累加和 cur 1最大答案 ans 1。读入 -3cur 1 (-3) -2。最大答案还是 1。这时候 cur 是负数按照贪心策略应该把 cur 重置为 0。为什么因为以 -3 结尾的这一段不但没有贡献还会拖累后面的数。如果后面有一个 4那1 -3 4的和是 2还不如直接4大。既然前面的累计是负的那不如把起点挪到当前数字本身重新开始。重置之后读入 4cur 0 4 4ans 更新为 4。读入 -1cur 4 (-1) 3ans 仍然是 4。现在 cur 虽然变小了但还不是负数所以保留。因为后面可能有更大的正数这段4 -1仍然有希望。读入 2cur 3 2 5ans 更新为 5。读入 1cur 5 1 6ans 更新为 6。读入 -5cur 6 (-5) 1ans 仍然是 6。最后输出 6。这个过程就是 Kadane 算法的直观版本cur永远表示“以当前位置结尾的最大子段和”。如果它变成负数就说明以当前位置结尾的子段不管从哪个起点开始都不划算干脆把 cur 归零让下一个数字作为新的起点。3.2 为什么“抛弃”不会漏掉最优解这里必须解释清楚一个核心问题把负数前缀扔掉会不会恰好把最优解的一部分扔掉了不会。我们可以这样想假设最优解是从起点 i 到终点 j 的一段那么对任意一个位置 k只要 i ≤ k ≤ j这段最优解在 k 处的前缀和一定不能是负数。为什么因为如果从 i 加到 k 的和是负数那我们不如直接从 k1 开始累加去掉这一段负数前缀剩下的和会更大。这与“从 i 到 j 是最优子段”矛盾。所以可以得出一个结论最优子段的任何一个合法前缀其累加和一定大于等于 0。这正好是贪心策略里“cur 为负就重置”的依据。我们在扫描过程中一旦发现当前累加和 cur 小于 0就可以断定“当前这一整段不可能成为最优解的前缀”于是把起点挪到下一个数。因为最优解的前缀永远不会为负所以这个贪心丢弃操作不会误伤正确答案。这个证明最好自己推一遍不要死记硬背。明白了这一点你就不是在背代码而是在掌握一个能迁移到其他贪心题里的思考方式。3.3 和动态规划的关系贪心决策是自顶向下的理解状态转移是数学表达很多同学会疑惑这个解法到底是贪心还是动态规划其实两种看法都成立。动态规划的写法是定义dp[i]表示以第 i 个元素结尾的最大子段和那么状态转移方程为dp[i] max(a[i], dp[i-1] a[i])意思是要么从第 i 个元素重新开始把dp[i-1]完全丢掉要么把 a[i] 接到前一个最优子段后面。最终答案是所有dp[i]的最大值。而前面说的贪心写法cur max(a[i], cur a[i])和cur a[i]; if (cur 0) cur 0;本质上就是在用实时更新的方式计算这个dp[i]。当你从“当前累加为负就重置”这个角度去理解时它就是贪心当你从“状态转移”的角度去理解时它就是动态规划。GESP 五级如果考到这道题你用哪种原理解释都能得分关键是要能说清楚自己的代码为什么是对的。4. C实现与易错点从能跑到AC4.1 标准 O(n) 代码这道题的标准解法我推荐下面这种写法#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; long long ans LLONG_MIN; long long cur 0; for (int i 0; i n; i) { long long x; cin x; cur max(x, cur x); ans max(ans, cur); } cout ans endl; return 0; }这段代码里cur表示以当前数字结尾的最大子段和。max(x, cur x)做了两件事如果cur x比 x 更大说明前面的子段对 x 有正贡献那就接上如果cur x还不如 x 本身说明前面的子段是累赘那就从 x 重新开始。ans记录历史上出现过的最大cur最后输出。这里不需要单独处理全负数的情况因为当 x 是负数时cur x会小于 xcur就会变成 x 本身ans 也会跟着更新成负数。最终输出的就是一个最大的负数。4.2 全负数序列的边界陷阱网上还有一种常见写法long long cur 0, ans 0; for (int i 0; i n; i) { long long x; cin x; cur x; ans max(ans, cur); if (cur 0) cur 0; }这个写法在大部分情况下是对的但遇到全负数序列时会输出 0而不是正确答案。比如序列是-1 -2 -3最大子段和应该是 -1但这个代码的 ans 会一直是 0。要修正也很简单先更新 ans再判断是否重置 cur。不过更稳妥的方式还是用cur max(x, cur x)这种写法天然规避了全负数的坑。为什么有人会在全负数上翻车因为他们把“cur 为负就重置”理解成了“答案一定非负”忘了题目要求“非空子段”。这也是我在改作业时反复强调的边界条件不要靠人肉记忆要用多组极端数据去验证。4.3 溢出、快读和常见调试经验关于溢出我建议一律用long long。这道题虽然 int 在极端数据下勉强够得着但很多变体题会把数据范围放大比如 a_i 到 10^9那样 int 直接各种溢出排查起来非常痛苦。养成用 long long 的习惯能省很多事。另外洛谷这类 OJ 环境下cin加ios::sync_with_stdio(false)和cin.tie(nullptr)也够用没必要强行写快读。但如果读入量更大或者你习惯用 scanf/printf也完全可以。我个人更喜欢ios::sync_with_stdio(false)加long long的组合代码清晰出 bug 的概率低。调试的时候我一般会准备几组极端数据全正数5 1 2 3 4 5期望输出 15。全负数3 -5 -2 -1期望输出 -1。单个元素1 -7期望输出 -7。正负交替7 1 -3 4 -1 2 1 -5期望输出 6。只要这几组过了这道题的正确性就基本稳了。5. 一题多解分治、线段树和变体思路5.1 分治解法跨过中点的子段怎么处理最大子段和还有一个经典的 O(n log n) 分治做法。把区间从中间切开最大子段和有三种可能完全在左半段完全在右半段或者跨过中点。完全在左半、完全在右半的部分可以递归求解。麻烦的是跨中点的部分它一定是由“从中点向左延伸的最大后缀和”加上“从中点向右延伸的最大前缀和”组成。这两部分可以分别从中间往两边扫一遍求出来。这里给一个简化的核心思路long long solve(int l, int r, vectorlong long a) { if (l r) return a[l]; int mid (l r) / 2; long long left solve(l, mid, a); long long right solve(mid 1, r, a); long long left_sum LLONG_MIN, cur 0; for (int i mid; i l; --i) { cur a[i]; left_sum max(left_sum, cur); } long long right_sum LLONG_MIN; cur 0; for (int i mid 1; i r; i) { cur a[i]; right_sum max(right_sum, cur); } return max({left, right, left_sum right_sum}); }分治解法在 GESP 考场上不一定需要但它能帮你在“一题多解”上打开思路。尤其是 GESP 五级喜欢考察对算法思想的灵活运用如果你能在注释里写上三种解法的适用情况会是很明显的加分项。5.2 线段树解法四个值的合并线段树也可以维护最大子段和每个节点需要存四样东西区间和 sum、区间最大前缀和 pre、区间最大后缀和 suf、区间最大子段和 mx。合并两个子节点时sum 左.sum 右.sumpre max(左.pre, 左.sum 右.pre)suf max(右.suf, 右.sum 左.suf)mx max(左.mx, 右.mx, 左.suf 右.pre)这种写法在遇到“单点修改、动态查询最大子段和”的题目时非常有用。P1115 本身是静态的不需要线段树但如果你能把线段树这版也写出来对 C 的数据结构储备会很有帮助。不过对 GESP 五级来说线段树可能超纲了解一下即可不必死磕。5.3 几个高频变体最大子矩阵、环形数组、至少连续 k 个元素最大子段和衍生题非常多我这里提三个最常见的最大子矩阵把每一行压缩成一个前缀和数组然后枚举行上下边界对列方向求最大子段和。复杂度 O(n^3)但 n 较小时很常用。环形数组最大子段和分两种情况一种是不跨越数组首尾直接求普通最大子段和另一种是跨越首尾等价于“数组总和减去最小子段和”。取两种情况的最大值。限制子段长度至少为 k在遍历右端点时维护一个滑动窗口内的最小前缀和然后用当前前缀和减掉窗口内的最小前缀和。这些变体题在洛谷上有很多比如 P1719 最大加权矩形就是最大子矩阵的模板题。如果你 P1115 吃透了后面遇到这些题会轻松很多。6. 给GESP五级考生的刷题建议6.1 不要只看题解要会做复杂度推导我见过太多孩子刷题的方式打开题解抄一遍代码提交 AC然后下一题。这样刷一百道题也很难形成能力。以 P1115 为例你应该自己从 O(n^3) 写到 O(n^2)再想想能不能 O(n)每一步都要能说清楚复杂度为什么降下来了。备考 GESP 五级扎实的复杂度意识比背题更重要。五级的题不会像 P1115 那么简单但一定会考你类似的能力拿到一个数据范围先判断需要什么复杂度再选择对应算法。如果只会复制代码遇到稍微改变一点条件的题就容易崩。6.2 错题记录和边界测试模板我自己的刷题习惯是准备一个错题本每道做错的题都记三行错在哪、为什么错、下次怎么避免。P1115 这题最常见的错误就是全负数输出 0 和 int 溢出。这类错误如果你不记录下次换一道变体题还会犯。另外建议给自己整理一个边界测试模板。多花三十秒测一下全正、全负、全零、单个元素、最大 n 这五类数据能帮你躲过大部分隐藏的坑。竞赛评测不会因为你“就差一点点”就给你分AC 就是 ACWA 就是 WA。6.3 一点个人体会从“背模板”到“想通原理”最后说点实际的。我辅导这些孩子时发现真正把 P1115 的原理想明白的人后面学贪心、学动态规划都会顺很多只背代码的人过了两天再让他写一遍十有八九写不出来。最大子段和这道题就像算法世界里的一把钥匙它把贪心、动态规划、分治、前缀和几个重要知识点都串到了一起。我建议你把这篇文章里的几种解法都自己敲一遍尤其要把“为什么负前缀要丢弃”这个证明写在代码注释旁边。等你有一天看到任何“找一段连续区间最值”的题目能条件反射地想到“能不能用 cur max(x, cur x)”这道题的价值才真正被你吸收进去了。
洛谷P1115最大子段和：从暴力到贪心的O(n)解法与C++实战
最近在帮一批准备 GESP C五级的孩子复盘算法题洛谷 P1115 最大子段和被问到的频率非常高。题目本身很“短平快”给一个长度为 n 的整数序列找出连续且非空的一段使它的和最大。但就是这道看起来简单的题能把贪心思想、时间复杂度优化、边界处理、甚至一题多解串起来。很多人第一次写这道题第一反应是枚举所有区间一提交就是 TLE然后去看题解背了一个“负数就清零”的写法却不理解为什么对。这篇文章我就从最暴力的思路开始推一步步推到 O(n) 的贪心解法再把全负数、溢出、变体和备考 GESP 五级的方法一起讲透。1. 这道题到底在考什么先看懂最大子段和1.1 从洛谷 P1115 的题面说起题面非常简短。第一行是一个正整数 n表示序列长度第二行是 n 个整数可能有正数、负数或零。要求在这 n 个数里找出一段连续的数字这段数字必须非空且所有元素之和最大输出这个最大值。举个例子n7序列是1 -3 4 -1 2 1 -5肉眼扫过去能找到的最大连续子段是4 -1 2 1加起来等于 6。这里是输出 6。注意题目说的是“连续且非空”这意味着你不能跳着选也不能一个都不选。如果序列全是负数你仍必须选一段长度为 1 的子段也就是选一个绝对值损失最小的负数。这种题目叫“最大子段和”也叫“最大连续子序列和”。它在算法题里属于基础中的基础但衍生题非常多比如最大子矩阵、环形数组最大子段和、带长度限制的最大子段和都建立在这道题的理解之上。1.2 数据范围先压死一半人的枚举思路洛谷 P1115 的 n 可以到 200000。这个数据范围意味着什么如果枚举所有区间区间数量大约是 n * (n1) / 2也就是大约 200 亿个肯定超时。就算用前缀和把区间求和优化到 O(1)枚举起点和终点仍然是 O(n^2)对 20 万的数据来说完全跑不动。很多人一开始写代码习惯用两层循环枚举区间左右端点甚至三层循环把中间元素再加一遍。这种思路在 n100 时没问题一旦到了 OJ 上的大数据直接 TLE。所以我一直跟学 C 的孩子说看完题目先别急着写代码先看数据范围心里得先有一个复杂度预算。n200000 的情况下O(n) 或 O(n log n) 是必须的O(n^2) 可以直接不用想。另外这题 a_i 的绝对值可以到 10^4n 最大 200000理论上最大总和能到 2×10^9已经贴近 int 的上限。所以代码里最好直接用 long long避免溢出把自己卡死。1.3 为什么它被归入“贪心思想”考点GESP 五级开始重点引入算法设计思想贪心是其中一个高频考点。最大子段和之所以常被拿来当贪心思想的例题是因为它藏着一个非常经典的“局部最优决策”从左往右累加一旦当前累加和变成负数就果断把它丢弃从下一个位置重新开始。这个决策看起来很“贪心”我不管后面有什么先把当前这一小段的利益最大化如果当前这段不仅没帮我赚钱还在拖后腿那就丢掉。最后再在所有“以某个位置结尾”的最大值里取一个最大的。严格来说Kadane 算法也经常被归为动态规划因为它对应一个状态转移方程。但这道题在不少教学材料和题目标签里都写“贪心思想”因为从理解方式上它确实是最容易讲清楚的贪心入门模型。2. 排除暴力从 O(n^3) 到 O(n^2) 的推演2.1 最直观的三重循环先看最直白的暴力写法#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint a(n 1); for (int i 1; i n; i) cin a[i]; long long ans LLONG_MIN; for (int i 1; i n; i) { for (int j i; j n; j) { long long sum 0; for (int k i; k j; k) sum a[k]; ans max(ans, sum); } } cout ans endl; return 0; }这段代码的思路是枚举左端点 i 和右端点 j然后再用一个 k 循环把区间 [i, j] 里的数全加起来。三层循环的复杂度是 O(n^3)。n200000 时这个复杂度几乎是天文数字运行时间不是几秒的问题而是几百年都跑不完。所以三重循环的唯一意义是帮自己理解题意绝对不能拿去提交。2.2 前缀和优化枚举起点和终点稍微聪明一点的做法是提前算好前缀和这样求任意区间的和只需要 O(1) 时间#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorlong long pref(n 1, 0); for (int i 1; i n; i) { long long x; cin x; pref[i] pref[i - 1] x; } long long ans LLONG_MIN; for (int i 1; i n; i) { for (int j i; j n; j) { long long sum pref[j] - pref[i - 1]; ans max(ans, sum); } } cout ans endl; return 0; }有了前缀和求[i, j]的和只需要pref[j] - pref[i-1]。但这里仍然是两层循环枚举所有区间复杂度 O(n^2)。二十万的数据量平方复杂度就是 400 亿次操作照样超时。不过这一版的价值不是能 AC而是让我们发现一个事实当我们固定右端点 j要算以 j 结尾的最大子段和本质是在问“左端点 i 在 1..j 之间哪个pref[i-1]最小”。因为pref[j] - pref[i-1]要最大减数pref[i-1]就要最小。这其实已经离贪心解法很近了。2.3 这轮推导给了我们什么提示从 O(n^3) 到 O(n^2)问题出在重复计算。我们明明可以一边读入一边处理却非要先把所有区间都枚举一遍。真正的高效解法应该避免枚举而是维护“以当前位置结尾的最大子段和”。这个思路一旦想通O(n) 就顺理成章了。我常在视频里跟学生讲复杂度的优化本质上是在消除无效劳动。三重循环枚举区间的无效劳动在于很多区间的和已经被反复计算过两重循环的无效劳动在于即使求和已经是 O(1)区间数量本身仍然太多。那么能不能不枚举右端点以外的所有左端点答案是可以的这就是贪心/动态规划解法。我们要在“读入一个数、更新一次答案”的过程中把最大子段和直接算出来。3. 贪心核心当前缀和为负数时果断抛弃3.1 从一次手算加深直觉先不写公式我们手算一遍上面的例子1 -3 4 -1 2 1 -5。从第一个数开始当前累加和 cur 1最大答案 ans 1。读入 -3cur 1 (-3) -2。最大答案还是 1。这时候 cur 是负数按照贪心策略应该把 cur 重置为 0。为什么因为以 -3 结尾的这一段不但没有贡献还会拖累后面的数。如果后面有一个 4那1 -3 4的和是 2还不如直接4大。既然前面的累计是负的那不如把起点挪到当前数字本身重新开始。重置之后读入 4cur 0 4 4ans 更新为 4。读入 -1cur 4 (-1) 3ans 仍然是 4。现在 cur 虽然变小了但还不是负数所以保留。因为后面可能有更大的正数这段4 -1仍然有希望。读入 2cur 3 2 5ans 更新为 5。读入 1cur 5 1 6ans 更新为 6。读入 -5cur 6 (-5) 1ans 仍然是 6。最后输出 6。这个过程就是 Kadane 算法的直观版本cur永远表示“以当前位置结尾的最大子段和”。如果它变成负数就说明以当前位置结尾的子段不管从哪个起点开始都不划算干脆把 cur 归零让下一个数字作为新的起点。3.2 为什么“抛弃”不会漏掉最优解这里必须解释清楚一个核心问题把负数前缀扔掉会不会恰好把最优解的一部分扔掉了不会。我们可以这样想假设最优解是从起点 i 到终点 j 的一段那么对任意一个位置 k只要 i ≤ k ≤ j这段最优解在 k 处的前缀和一定不能是负数。为什么因为如果从 i 加到 k 的和是负数那我们不如直接从 k1 开始累加去掉这一段负数前缀剩下的和会更大。这与“从 i 到 j 是最优子段”矛盾。所以可以得出一个结论最优子段的任何一个合法前缀其累加和一定大于等于 0。这正好是贪心策略里“cur 为负就重置”的依据。我们在扫描过程中一旦发现当前累加和 cur 小于 0就可以断定“当前这一整段不可能成为最优解的前缀”于是把起点挪到下一个数。因为最优解的前缀永远不会为负所以这个贪心丢弃操作不会误伤正确答案。这个证明最好自己推一遍不要死记硬背。明白了这一点你就不是在背代码而是在掌握一个能迁移到其他贪心题里的思考方式。3.3 和动态规划的关系贪心决策是自顶向下的理解状态转移是数学表达很多同学会疑惑这个解法到底是贪心还是动态规划其实两种看法都成立。动态规划的写法是定义dp[i]表示以第 i 个元素结尾的最大子段和那么状态转移方程为dp[i] max(a[i], dp[i-1] a[i])意思是要么从第 i 个元素重新开始把dp[i-1]完全丢掉要么把 a[i] 接到前一个最优子段后面。最终答案是所有dp[i]的最大值。而前面说的贪心写法cur max(a[i], cur a[i])和cur a[i]; if (cur 0) cur 0;本质上就是在用实时更新的方式计算这个dp[i]。当你从“当前累加为负就重置”这个角度去理解时它就是贪心当你从“状态转移”的角度去理解时它就是动态规划。GESP 五级如果考到这道题你用哪种原理解释都能得分关键是要能说清楚自己的代码为什么是对的。4. C实现与易错点从能跑到AC4.1 标准 O(n) 代码这道题的标准解法我推荐下面这种写法#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; long long ans LLONG_MIN; long long cur 0; for (int i 0; i n; i) { long long x; cin x; cur max(x, cur x); ans max(ans, cur); } cout ans endl; return 0; }这段代码里cur表示以当前数字结尾的最大子段和。max(x, cur x)做了两件事如果cur x比 x 更大说明前面的子段对 x 有正贡献那就接上如果cur x还不如 x 本身说明前面的子段是累赘那就从 x 重新开始。ans记录历史上出现过的最大cur最后输出。这里不需要单独处理全负数的情况因为当 x 是负数时cur x会小于 xcur就会变成 x 本身ans 也会跟着更新成负数。最终输出的就是一个最大的负数。4.2 全负数序列的边界陷阱网上还有一种常见写法long long cur 0, ans 0; for (int i 0; i n; i) { long long x; cin x; cur x; ans max(ans, cur); if (cur 0) cur 0; }这个写法在大部分情况下是对的但遇到全负数序列时会输出 0而不是正确答案。比如序列是-1 -2 -3最大子段和应该是 -1但这个代码的 ans 会一直是 0。要修正也很简单先更新 ans再判断是否重置 cur。不过更稳妥的方式还是用cur max(x, cur x)这种写法天然规避了全负数的坑。为什么有人会在全负数上翻车因为他们把“cur 为负就重置”理解成了“答案一定非负”忘了题目要求“非空子段”。这也是我在改作业时反复强调的边界条件不要靠人肉记忆要用多组极端数据去验证。4.3 溢出、快读和常见调试经验关于溢出我建议一律用long long。这道题虽然 int 在极端数据下勉强够得着但很多变体题会把数据范围放大比如 a_i 到 10^9那样 int 直接各种溢出排查起来非常痛苦。养成用 long long 的习惯能省很多事。另外洛谷这类 OJ 环境下cin加ios::sync_with_stdio(false)和cin.tie(nullptr)也够用没必要强行写快读。但如果读入量更大或者你习惯用 scanf/printf也完全可以。我个人更喜欢ios::sync_with_stdio(false)加long long的组合代码清晰出 bug 的概率低。调试的时候我一般会准备几组极端数据全正数5 1 2 3 4 5期望输出 15。全负数3 -5 -2 -1期望输出 -1。单个元素1 -7期望输出 -7。正负交替7 1 -3 4 -1 2 1 -5期望输出 6。只要这几组过了这道题的正确性就基本稳了。5. 一题多解分治、线段树和变体思路5.1 分治解法跨过中点的子段怎么处理最大子段和还有一个经典的 O(n log n) 分治做法。把区间从中间切开最大子段和有三种可能完全在左半段完全在右半段或者跨过中点。完全在左半、完全在右半的部分可以递归求解。麻烦的是跨中点的部分它一定是由“从中点向左延伸的最大后缀和”加上“从中点向右延伸的最大前缀和”组成。这两部分可以分别从中间往两边扫一遍求出来。这里给一个简化的核心思路long long solve(int l, int r, vectorlong long a) { if (l r) return a[l]; int mid (l r) / 2; long long left solve(l, mid, a); long long right solve(mid 1, r, a); long long left_sum LLONG_MIN, cur 0; for (int i mid; i l; --i) { cur a[i]; left_sum max(left_sum, cur); } long long right_sum LLONG_MIN; cur 0; for (int i mid 1; i r; i) { cur a[i]; right_sum max(right_sum, cur); } return max({left, right, left_sum right_sum}); }分治解法在 GESP 考场上不一定需要但它能帮你在“一题多解”上打开思路。尤其是 GESP 五级喜欢考察对算法思想的灵活运用如果你能在注释里写上三种解法的适用情况会是很明显的加分项。5.2 线段树解法四个值的合并线段树也可以维护最大子段和每个节点需要存四样东西区间和 sum、区间最大前缀和 pre、区间最大后缀和 suf、区间最大子段和 mx。合并两个子节点时sum 左.sum 右.sumpre max(左.pre, 左.sum 右.pre)suf max(右.suf, 右.sum 左.suf)mx max(左.mx, 右.mx, 左.suf 右.pre)这种写法在遇到“单点修改、动态查询最大子段和”的题目时非常有用。P1115 本身是静态的不需要线段树但如果你能把线段树这版也写出来对 C 的数据结构储备会很有帮助。不过对 GESP 五级来说线段树可能超纲了解一下即可不必死磕。5.3 几个高频变体最大子矩阵、环形数组、至少连续 k 个元素最大子段和衍生题非常多我这里提三个最常见的最大子矩阵把每一行压缩成一个前缀和数组然后枚举行上下边界对列方向求最大子段和。复杂度 O(n^3)但 n 较小时很常用。环形数组最大子段和分两种情况一种是不跨越数组首尾直接求普通最大子段和另一种是跨越首尾等价于“数组总和减去最小子段和”。取两种情况的最大值。限制子段长度至少为 k在遍历右端点时维护一个滑动窗口内的最小前缀和然后用当前前缀和减掉窗口内的最小前缀和。这些变体题在洛谷上有很多比如 P1719 最大加权矩形就是最大子矩阵的模板题。如果你 P1115 吃透了后面遇到这些题会轻松很多。6. 给GESP五级考生的刷题建议6.1 不要只看题解要会做复杂度推导我见过太多孩子刷题的方式打开题解抄一遍代码提交 AC然后下一题。这样刷一百道题也很难形成能力。以 P1115 为例你应该自己从 O(n^3) 写到 O(n^2)再想想能不能 O(n)每一步都要能说清楚复杂度为什么降下来了。备考 GESP 五级扎实的复杂度意识比背题更重要。五级的题不会像 P1115 那么简单但一定会考你类似的能力拿到一个数据范围先判断需要什么复杂度再选择对应算法。如果只会复制代码遇到稍微改变一点条件的题就容易崩。6.2 错题记录和边界测试模板我自己的刷题习惯是准备一个错题本每道做错的题都记三行错在哪、为什么错、下次怎么避免。P1115 这题最常见的错误就是全负数输出 0 和 int 溢出。这类错误如果你不记录下次换一道变体题还会犯。另外建议给自己整理一个边界测试模板。多花三十秒测一下全正、全负、全零、单个元素、最大 n 这五类数据能帮你躲过大部分隐藏的坑。竞赛评测不会因为你“就差一点点”就给你分AC 就是 ACWA 就是 WA。6.3 一点个人体会从“背模板”到“想通原理”最后说点实际的。我辅导这些孩子时发现真正把 P1115 的原理想明白的人后面学贪心、学动态规划都会顺很多只背代码的人过了两天再让他写一遍十有八九写不出来。最大子段和这道题就像算法世界里的一把钥匙它把贪心、动态规划、分治、前缀和几个重要知识点都串到了一起。我建议你把这篇文章里的几种解法都自己敲一遍尤其要把“为什么负前缀要丢弃”这个证明写在代码注释旁边。等你有一天看到任何“找一段连续区间最值”的题目能条件反射地想到“能不能用 cur max(x, cur x)”这道题的价值才真正被你吸收进去了。
