先解释一下题目洛谷P1115最大子段和。给定一个长度为 n 的整数序列要求找出一个连续的非空子段使得该子段所有数之和最大输出这个最大值。比如样例7 -2 11 -4 13 -5 -2肉眼扫一遍最大的一段是从 11 到 13也就是 11 (-4) 13 20。这道题在洛谷上是普及/提高- 的难度但它一点都不“入门级”。它背后牵扯出的动态规划状态设计、贪心思维、分治思想是后续一大票区间类问题的地基。很多人在刷这道题之前觉得动态规划很玄学刷完之后才明白DP 其实就是用一种“有组织的枚举”替代了暴力枚举。这篇文章我会从暴力思路开始推演一步步走到动态规划、贪心、分治并给出完整的 AC 代码和提交时的实战经验。如果你刚开始接触算法竞赛或者想彻底吃透最大子段和这一类问题这篇题解应该能帮到你。1. 题目分析与核心思路拆解1.1 看清题目真正要考察什么P1115 的核心信息就几个连续、非空、最大和。子段不能跳着选也不能选空段。这两个限制条件看似简单实际上藏着三个关键点第一子段必须连续。这意味着你不能排序后挑一些正数加起来所有解法都必须在一个连续的区间内做文章。第二序列中可能存在负数负数不是障碍它考验的是你在“终止一段”和“延续一段”之间如何做决策。第三子段非空。这句话直接决定了当所有数字都是负数时的输出结果应该是最大的那个负数而不是 0。很多人做完这题后遇到类似问题还是会犯迷糊根子就在于没有把题目约束条件抽象成数学定义。真正的算法题解从来不是上来就写代码而是先把题目里的每个限制条件转化成状态转移方程或算法决策里的一个分支条件。1.2 数据范围决定你能用什么复杂度P1115 的 n 最大值是 2×10^5也就是 20 万个整数。这是整个题目最核心的约束条件。如果你没看数据范围直接上两层循环枚举所有子段那么子段个数大约是 n(n1)/2代入 n 200000结果大约是 2×10^10也就是两百亿个子段。哪怕每个子段只做一次加法在普通评测机上也要跑几十秒甚至几分钟。洛谷的时间限制通常是 1 秒暴力解法必挂 TLE。所以这道题的所有正解复杂度必须是 O(n log n) 或者 O(n)。换句话说你必须在扫描一遍或者少量扫描的过程中就完成最大子段和的计算不能把子段枚举完再算。理解了这个约束你才会明白为什么动态规划在这里是“必须的”而不是“技巧上的炫技选项”。2. 从暴力枚举到动态规划的思维演变2.1 先用前缀和感受一下暴力瓶颈很多初学者拿到这题会想那我用前缀和优化一下先预处理出 pre[i] 表示前 i 个数的总和然后枚举左端点 l 和右端点 r用 pre[r] - pre[l-1] 快速得到任意子段的和。这个思路本身没毛病单次区间求和从 O(n) 降到了 O(1)但枚举左右端点仍然是 O(n^2) 的复杂度。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint a(n 1), pre(n 1, 0); for (int i 1; i n; i) { cin a[i]; pre[i] pre[i - 1] a[i]; } int ans INT_MIN; for (int l 1; l n; l) { for (int r l; r n; r) { ans max(ans, pre[r] - pre[l - 1]); } } cout ans endl; return 0; }这段代码在 n 很小时能跑出正确结果但在 P1115 上必超时。它给我们的重要教训是前缀和只解决了“快速求区间和”的问题没有解决“快速找到最优区间”的问题。算法优化的关键在于减少需要尝试的方案数量而不是让每个方案算得更快。2.2 换一个问法答案自己就出来了暴力枚举的核心问题在于我们把整个序列中所有连续子段都当作独立的候选对象。但如果我们换一个角度不考虑以 l 开头而是考虑以某个位置 i 结尾的所有子段。这样一来所有子段被划分成了 n 类第 i 类就是以 i 结尾的子段。对于第 i 类它的最大和到底怎么求如果以 i 结尾那么这些子段要么只包含 a[i] 一个元素要么是在某个以 i-1 结尾的子段后面接上 a[i]。而“以 i-1 结尾的所有子段中最大和”本身也是一个同类子问题记作 dp[i-1]。于是就有了状态转移方程dp[i] max(a[i], dp[i-1] a[i])dp[i] 表示以第 i 个元素作为子段最后一个元素时能获得的最大子段和。最终答案是在所有 dp[i] 中取最大值。这个推导过程本质上就是把原本需要在二维空间里枚举的左右端点压缩成了一维的状态转移。动态规划最迷人的地方就在这它看起来像是在“凭空设计状态”实际上只是换了一个更聪明的划分方式让子问题之间形成可以利用的依赖关系。3. 动态规划代码实现与细节打磨3.1 滚动数组把 O(n) 空间压到 O(1)有了状态转移方程第一版 DP 代码非常容易写开一个 dp 数组从 1 扫到 n。但仔细观察dp[i] 只依赖 dp[i-1]完全没必要保留整个 dp 数组。用一个变量 cur 表示以当前位置结尾的最大子段和再用一个变量 ans 追踪历史最大值就能把空间复杂度降到 O(1)。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; long long cur 0, ans LLONG_MIN; 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; }这就是滚动数组的思想在状态转移只依赖相邻几个状态的时候不需要保留整个 DP 表只用几个变量滚动更新即可。很多初学者一开始不敢这么写怕丢掉前面的信息。但其实这里我们只关心“以当前结尾的最大值”和“全局最大值”历史信息早就被 ans 这个变量记住了不需要回头再看一遍 dp 数组。3.2 为什么要用 long long 而不是 int这是这道题一个非常容易踩的坑。虽然题目没有特别说明数字范围但 n 最大到 2×10^5如果所有数字都是正数且每个数字接近 10^4那么最大子段和可以达到 2×10^9 左右。int 的最大值是约 2.147×10^9在这个边界上极其危险一旦超过就会溢出导致答案为负数wa 到怀疑人生。我见过不少人在 P1115 上用 int 也 AC 了因为测试数据没卡到这个极端情况。但作为算法选手写代码时不应该赌数据不极端。直接把 cur 和 ans 声明为 long long成本几乎为零却能避免一整类溢出问题。这种“防御性编程”习惯在后面的区间题目里会更常用到。注意如果你在洛谷上 WA 并怀疑是溢出最简单的验证方法就是输出中间变量 cur 的最大值看看是否接近 int 上限。如果接近甚至超过果断换 long long。4. 贪心视角Kadane算法的本质4.1 累加过程中一旦变负就丢掉除了 DP最大子段和还有一种更直观的贪心写法叫 Kadane 算法。逻辑非常朴素从左到右遍历用一个变量 sum 维护当前累加的子段和。每遍历到一个元素先把它加进 sum更新答案如果 sum 变成负数说明这一段子段对后续元素没有任何正贡献直接清零从下一个元素重新开始。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; long long sum 0, ans LLONG_MIN; for (int i 0; i n; i) { long long x; cin x; sum x; ans max(ans, sum); if (sum 0) sum 0; } cout ans endl; return 0; }这段代码几乎和 DP 版本一样简洁。贪心版本的“为什么对”可以从交换论证的角度理解如果当前累加和已经是负数那么它作为前缀放在任何后续子段前面都会拉低总和所以把它丢掉一定不会让答案变得更差。这个局部最优决策不会影响全局最优因为保留一个负前缀永远不会是未来最优解的一部分。4.2 DP 和贪心不过是同一枚硬币的两面对比一下两个版本的核心更新语句DP: cur max(x, cur x) 贪心: sum x; if (sum 0) sum 0;看起来不一样但数学上完全等价。cur max(x, cur x) 的意思是要么从 x 重新开始要么延续之前的子段。贪心版本里sum 加上 x 后如果小于 0赋值为 0相当于丢弃了“从更早位置开始的累积”。下一次再累加时效果就是“从下一个位置重新开始”这和 cur max(x, curx) 一旦 curx 小于 x 就选择 x 的行为完全一致。理解这一点非常重要。很多人认为动态规划和贪心是两种互斥的思想但在很多看似不同的算法里它们的本质是相通的。Kadane 算法既可以被解释成贪心也可以被称为“滚动状态的动态规划”。带着这层理解去刷题你会慢慢发现算法的高阶套路其实并不算多很多问题都是同一类思维在不同场景下的变体。5. 分治解法与常见问题排查5.1 分治法的实现思路除了 O(n) 的 DP 和贪心最大子段和还有一个经典的 O(n log n) 分治写法。虽然性能不如 O(n)但分治思路能帮你在后续处理线段树合并区间信息时打下良好基础。把序列从中间 mid 劈成两半那么整个序列的最大子段和只可能出现在三个位置完全在左半边、完全在右半边、横跨左右两半。前两种情况递归求解即可第三种情况需要从 mid 出发单独向左扫描找出最大后缀和再单独向右扫描找出最大前缀和两个值相加就是横跨答案。#include bits/stdc.h using namespace std; const int N 200005; long long a[N]; long long crossSum(int l, int mid, int r) { long long leftMax LLONG_MIN, sum 0; for (int i mid; i l; i--) { sum a[i]; leftMax max(leftMax, sum); } long long rightMax LLONG_MIN; sum 0; for (int i mid 1; i r; i) { sum a[i]; rightMax max(rightMax, sum); } return leftMax rightMax; } long long solve(int l, int r) { if (l r) return a[l]; int mid (l r) 1; long long leftAns solve(l, mid); long long rightAns solve(mid 1, r); long long crossAns crossSum(l, mid, r); return max({leftAns, rightAns, crossAns}); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; for (int i 0; i n; i) cin a[i]; cout solve(0, n - 1) endl; return 0; }分治法每次递归把区间分成两半每次合并时 crossSum 需要线性扫描一遍该区间因此总复杂度是 T(n) 2T(n/2) O(n)解得 O(n log n)。在 P1115 的数据范围内这个复杂度完全够用。5.2 洛谷提交常见的几个错误我在刷题群和帮人 review 代码时总结了几个在 P1115 上最容易犯的错误整理成一张表错误现象根本原因解决办法全负数样例输出 0把 ans 初始化为 0 了把 ans 初始化为 LLONG_MIN 或 a[0]大样例 WA使用 int 导致溢出变量类型改为 long longTLE 超时使用 O(n^2) 枚举换 DP/贪心/分治法RE 报错数组开小了或越界访问数组开 n1 大小注意下标其中全负数样例是最容易踩的。序列-5 -3 -7的正确最大子段和是 -3但如果你把 ans 初始化为 0代码会一直输出 0因为 cur x 后 cur 始终是负数max(0, 负数)始终是 0。这其实就是把“允许选择空子段”的假设错误地带进了题目。题目明确要求非空所以答案必须存在于某个实际元素中。5.3 提交前的自查清单刷题久了你会发现很多 WA 并不是算法思路问题而是输入输出或细节处理问题。我建议在提交 P1115 之前手动跑这几个测试用例全负数3 -5 -3 -7预期 -3单个元素1 42预期 42全正数4 1 2 3 4预期 10正负交替7 -2 11 -4 13 -5 -2预期 20这四个样例基本能覆盖掉大多数边界情况。如果这四个都过了再顺手检查一下变量类型是不是 long long 以及输入输出是否关闭了同步。这套自查流程在刷任何一道普通算法题时都适用省下来的时间远远超过多写几个测试样例的时间。提示如果你喜欢用 C 的 scanf/printf也完全没问题。P1115 用 scanf 和 cin 都能过关键是别在算法复杂度上翻车。6. 从P1115到后续算法题的扩展思维6.1 这道题还能怎么变最大子段和是一个基础模型很多题目都是在它上面加限制条件或者换查询场景询问多次区间最大子段和可以用线段树维护区间和、区间最大前缀和、区间最大后缀和、区间最大子段和四个值合并。环上的最大子段和把问题拆成“答案在环内部”和“答案跨过环头尾”两种情况后者等价于求最小子段和。带修改的最大子段和洛谷P4513等题就是 P1115 的线段树动态版本。如果你能把 P1115 的 DP 和分治彻底想透再去看线段树版本的区间合并就会发现合并的思路和分治法的跨中点扫描一模一样。这也是为什么我会建议你把分治法的代码也写一遍而不是只背 DP 完事。6.2 动态规划状态设计的普适套路最后分享一个我对动态规划状态设计的心得。很多人觉得 DP 难是因为不知道 dp 数组里到底要存什么。P1115 给了一个很重要的示范它把“以任意 l 开头、r 结尾的最大子段”转换成了“以 i 结尾的最大子段”。这背后的通用套路是面对区间、子序列问题时先想办法枚举一个固定端点把二维区间问题压缩成一维状态转移问题。以后做最长上升子序列、最大子矩阵和、最长公共子序列这类题时你会发现同样的套路反复出现固定右端点用左端点或上一个状态来建立依赖关系。你不需要背一整套 DP 模板只需要在读完题目后问自己一句如果强制要求某个位置必须是结尾我能不能写出当前状态和上一个状态的关系这句话是我刷了上百道 DP 题之后觉得最实用的一条心法。上面这些就是我在 P1115 这道题上刷题、调试、帮人 review 代码时积攒下来的全部干货。如果你一次 AC 了那说明你的思路已经比较到位如果卡住了也别沮丧把 DP、贪心、分治三种解法都亲手敲一遍感受一下它们怎么殊途同归收获绝对比单纯看题解大得多。