1. 写在最前最大连续子序列为什么值得单独写一篇1.1 这道题是什么刷算法题绕不开最大连续子序列某OJ的1231号题把这个经典问题又加了点佐料不只是让你求最大连续子段和还要把最大连续子序列对应的首尾元素输出出来。很多人第一次交WA不是算法不会而是卡在“到底输出谁”和“全负数怎么办”上。这篇文章从题意、状态转移、代码实现、排错到变体把这道题真正讲透。刚学动态规划的同学可以把它当入门练习已经刷过题的老手也不妨对照一下自己的边界处理是否干净。最大连续子序列也叫最大子段和是线性动态规划里最基础的模型之一。问题描述很简单给定一个长度为n的整数序列找一个连续区间让区间内所有数字的和最大。比如序列[-2, 11, -4, 13, -5, -2]最大和是20对应的区间是[11, -4, 13]首尾元素分别是11和13。这类问题看起来不值一提但它背后的状态定义、滚动变量、边界判断会直接复用到很多其他题目上。1.2 适合谁读这篇文章适合两类人。第一类是刚接触动态规划的初学者可以从零理解为什么状态转移方程长这样为什么需要临时左端点第二类是准备面试或者刷题复习的老手可以直接跳到错误排查和变体部分重点看那些平时容易忽略的细节。文章里的代码用C写用的是最直接的C风格输入输出在大多数在线评测环境下都能直接跑。2. 题意拆解题目到底在问什么2.1 输入输出格式与返回值细节题目输入是先给一个n表示这一组数据有n个整数接着给出这n个整数中间用空格或者换行分隔都可以。每次读到一个n为0时程序结束。每一组输出一行三个数字最大连续子序列的和、这个子序列的第一个元素、这个子序列的最后一个元素。这里有个容易忽视的约定如果序列里所有数都小于0则输出0以及整个序列的第一个元素和最后一个元素。先说清楚连续子序列是什么。它就是原数组中连续的一段不能跳着取。比如数组[-2, 11, -4, 13, -5, -2]最大连续子序列是[11, -4, 13]和是20不是[11,13]24因为中间隔着-4。最大子段和这个术语说的就是区间和的最大值DP里通常叫最大子段和问题。再看一个具体输出例子。如果输入是6 -2 11 -4 13 -5 -2输出应该是20 11 13。20是最大和11是子序列的第一个元素13是最后一个元素。这里最后一个13在数组里下标是3不是最后那个-2。很多人把输出端点错记成原数组端点直接输出20 11 -2必错。2.2 返回值为什么是元素而不是下标有些选手习惯返回下标比如输出20 1 3觉得逻辑没问题。但这题要求输出元素值所以printf那里必须写成a[left]、a[right]。这个细节一旦看漏代码写得再漂亮也过不了。还有一个隐藏约定是解的唯一性。如果最大和对应多个区间多数题目要求输出靠前的那一个。以数组[5, -10, 6]为例最大和是6对应子序列[6]靠前的位置就是下标2但如果有另一个同样和的出现就应该保留先出现的那组。代码里体现在更新答案时用大于而不是大于等于。这道题适合做动态规划入门的第二道题是因为它比单纯求最大值多一个记录位置的要求。很多人会为了省事把这道题当成贪心题其实非常容易漏边界。后面我会详细解释为什么不能直接维护一个区间答案。3. 核心原理最大子段和的状态转移3.1 为什么不能直接暴力先估算复杂度。暴力做法枚举左端i和右端j再循环k求i到j的和复杂度O(n^3)。用前缀和优化以后枚举区间还是O(n^2)当n到10万甚至百万级别完全跑不动。OJ上的老题数据可能不大但正确习惯是按最坏情况估计。分治可以做到O(n log n)把数组从中间劈开答案要么在左半、右半要么横跨中间。横跨部分需要从中间向左找最大后缀和、向右找最大前缀和加起来就是跨越答案。这个思路不难但实现要细心尤其处理全负数不如DP直观。DP用O(n)就能解决代码量还更少所以优先学DP。3.2 一维状态定义与状态转移方程DP的核心是定义状态。设dp[i]表示以第i个元素结尾的连续子段的最大和。注意“结尾”不是“任意区间”。正因为必须以i结尾才能确保子段的连续性也才能从i-1递推过来。状态转移只有两个选择把a[i]接到dp[i-1]对应的那段后面或者让a[i]自己单独开头。用公式写就是dp[i] max(dp[i-1] a[i], a[i])为什么不是dp[i-1]因为为了连续必须包含a[i]如果dp[i-1]是负数接上它只会拖累a[i]所以不如从a[i]重新开始。最终答案是所有dp[i]的最大值也就是max(dp[0], ..., dp[n-1])。注意不是dp[n-1]因为最大子序列不一定要在最后一个位置结束可能中间某一段的尾部已经是最大和了。拿[-2, 11, -4, 13, -5, -2]手推一下dp[0]-2dp[1]max(11, -211)11dp[2]max(-4, 11-4)7dp[3]max(13, 713)20dp[4]max(-5, 20-5)15dp[5]max(-2, 15-2)13。最大值是dp[3]20整个推导过程一目了然。3.3 滚动优化与常用贪心写法dp[i]只依赖dp[i-1]所以不需要保存一整个数组用一个cur变量滚动即可。cur表示当前以i结尾的最大和best表示历史全局最大和。每次循环先决定cur再更新bestlong long cur 0, best LLONG_MIN; for (int i 0; i n; i) { if (cur 0) cur a[i]; else cur a[i]; if (cur best) best cur; }这里的关键判断是cur 0。当cur小于0时它作为前缀对后面的段没有任何正面贡献。一个生活化的类比是你手里有一笔亏损的账继续往里投钱不如把账清零从下一个项目重新开始。这个O(n)写法解决的正是最大子段和问题在不少资料里也被称作最大子段和的贪心模板本质上和DP是同一个东西。注意初始值。cur初始为0这样第一个元素会走else分支cur变成a[0]best初始化成LLONG_MIN确保全负数时也能更新成最大的负数。如果你想用best 0全负数时结果会错成0。3.4 记录首尾下标的完整推导现在要输出首尾元素需要多维护三个变量left是最终答案的左端点right是右端点tmpLeft是当前候选段的起点。候选起点和最终答案起点不能混用。long long best LLONG_MIN, cur 0; int left 0, right 0, tmpLeft 0; for (int i 0; i n; i) { if (cur 0) { cur a[i]; tmpLeft i; } else { cur a[i]; } if (cur best) { best cur; left tmpLeft; right i; } }cur 0时我们把cur重置成a[i]同时tmpLeft i。注意left没有马上改。为什么因为cur重置后best可能仍然是历史最大值此时当前候选段还没有资格成为答案。只有在cur best也就是当前段刷新了历史纪录时才把left更新为tmpLeft。如果提前改了left就会出现best对应的区间和left没对应上。right的更新相对简单只要best刷新right一定是当前的i因为cur对应的是以i结尾的段。这段代码已经能正确处理全负数以外的所有数据包括数组全部为正、有0、有负但最大和为正等等。4. 参考代码与逐段讲解4.1 完整代码能过样例的版本下面是一份可以直接提交的完整代码包含全负数判断、最大子段和计算、首尾元素输出#include cstdio #include climits const int MAXN 100005; int main() { int n; while (scanf(%d, n) 1 n ! 0) { int a[MAXN]; bool allNegative true; for (int i 0; i n; i) { scanf(%d, a[i]); if (a[i] 0) allNegative false; } if (allNegative) { printf(0 %d %d\n, a[0], a[n - 1]); continue; } long long cur 0; long long best LLONG_MIN; int left 0, right 0, tmpLeft 0; for (int i 0; i n; i) { if (cur 0) { cur a[i]; tmpLeft i; } else { cur a[i]; } if (cur best) { best cur; left tmpLeft; right i; } } printf(%lld %d %d\n, best, a[left], a[right]); } return 0; }这段代码做到了一件事把题意里的每个约定都翻译成了显式逻辑。全负数单独处理避免后续输出端点被干扰非全负数走标准DP用long long防止溢出left和right只在best刷新时更新保证答案区间和最大和严格匹配。4.2 逐段讲解输入、判断、循环先看输入部分。while (scanf(%d, n) 1 n ! 0) 这句有两个作用一是读入n二是判断n不为0。scanf返回成功读到的变量个数等于1说明读到了整数如果文件末尾返回EOF循环自然停止。有些写法while(scanf(%d, n), n)在EOF时会出问题不推荐。接下来读入数组时同时用一个allNegative标记记录是否全负。只要有一个a[i] 0allNegative就变成false。这个标记的意义是题目规定全负时不输出最大负数而是输出0和整个序列的首元素、尾元素。你可以循环结束后判断best 0但提前标记更容易读懂。如果不是全负就进入DP循环。cur初始0best初始LLONG_MIN。这里我使用long long而不是int因为连续子段和虽然原题数据不大但不定长多组数据下中间结果有可能超过int范围。用long long不会影响时间但安全不少。4.3 为什么全负要单独拿掉如果不做allNegative判断循环结束以后best会变成所有负数里最大的那个。比如[-1,-2,-3]best-1。此时你直接输出best就和题目要求矛盾了。我见过不少人在循环后加一句if (best 0) printf(0 %d %d\n, a[0], a[n-1])这也是对的因为所有数全负等价于best 0。单独标记的好处是不会让DP循环里出现负数答案去影响left/right。还有一个细节n1且a[0]为负数时allNegative为true输出0 a[0] a[0]也就是0和同一个数输两次。这个输出有些怪但题目就是这么约定的。如果a[0]为正输出a[0] a[0] a[0]。样例有1 0时因为0是非负不存在全负DP中cur0best0leftright0输出0 0 0。4.4 输入输出效率问题这道题是多组输入n可能比较大。用cin/cout也可以但记得加ios::sync_with_stdio(false)和cin.tie(nullptr)。如果你直接用printf/scanf一般不用考虑同步问题。C风格输出的另一个好处是格式控制直观%d对应int%lld对应long long。如果发现输出格式错误先检查类型。printf(%lld %d %d\n, best, a[left], a[right]) 中best是long long用%llda[left]和a[right]是int用%d。有的Windows本地环境可能要求%I64d但通常评测环境是Linux用%lld就行。5. 常见错误速查表WA的九种姿势5.1 表格形式的问题排查我实际刷题时基本上把下面的错误全踩过一遍。遇到WA建议从上往下逐条对照错误类型现象原因解决全负数处理缺失输出最大负数没理解题目约定加allNegative标记或if(best0)输出下标输出20 1 3题目要求元素printf输出a[left] a[right]起点更新过早最大和对应区间错乱在cur重置时改left用tmpLeftbest刷新再更新left用int存和值大样例WA或溢出中间和超过int用long longright未更新right始终是初始值只在best刷新时更新right更新best时统一rightin0越界访问a[0]报错没处理结束while条件包含n!0多组数据变量未重置第二组输出异常best/left定义在while外在while内定义变量更新用同和解取后出现题目要求靠前用更新cin未优化TLEIO慢scanf/printf或关同步前三个是逻辑错误中间两个是数据范围和类型最后两个是比赛习惯问题。前两个直接决定你能不能过样例第三个则是这道题最坑的地方很多人算法全会代码也对就因为left更新太早而WA。5.2 一个容易被忽略的写法cur 0 和 cur a[i] 0我看到过一种错误把重置条件写成if (cur a[i] 0)。举个例子数组里有前置负段比如前面累积cur-2当前位置a[i]5。如果按cur a[i] 0判断-253不小于0于是走elsecur变成3但如果按正确写法cur 0判断前一段是-2应该重置从5开始cur变成5。显然正确的才能拿到更大值。所以在循环里必须在加入a[i]之前先看cur是不是负数。如果为负就直接放弃前面的段。这是这类最大子段和写法的精髓也是和普通前缀和最大的区别。前缀和是把所有数字都算进去而这里允许丢弃前面拖后腿的部分。5.3 免费边界测试数据我整理了几组必测数据提交前可以先用本地运行一遍6 -2 11 -4 13 -5 -2期望输出20 11 133 -1 -2 -3期望输出0 -1 -31 0期望输出0 0 04 2 -1 3期望输出4 2 34 5 -10 6 1期望输出7 6 14 -1 0 -2 1期望输出0 0 0这些用例分别覆盖了普通情况、全负数、n1、有0、负数开头、多个解。新手在提交前先用这几组跑一遍能过滤掉一半以上的低级错误。我强烈建议再写一个暴力枚举函数用于对拍随机生成数据对比结果这是排查DP题最快的办法。6. 从这道题看动态规划的通用套路6.1 状态定义的三要素这道题虽然简单但完整展示了动态规划的三个关键步骤。第一步是选状态dp[i]表示以第i个元素结尾的最大和第二步是写转移dp[i] max(dp[i-1] a[i], a[i])第三步是定边界比如cur初始0、best初始LLONG_MIN、全负单独处理。状态定义特别重要。同样是最大连续子序列如果状态定义成“前i个元素中的最大子段和”转移就会变得很别扭因为你不知道最后一个元素到底取没取也就没法连续。反过来定义成“以i结尾”下一个元素想接上来就非常自然。以后遇到类似问题先想想能不能用“以位置i为终点”的状态表达。很多看似复杂的DP题其实就是在这里换花样。比如最长上升子序列状态定义就是dp[i]表示以第i个数结尾的最长上升子序列长度最大连续乘积子数组也是以i结尾只是要多维护一个最小值。把这道题的思路吃透一大片线性DP题都能触类旁通。6.2 边界条件的检查清单边界条件往往是WA的重灾区。以这道题为例建议以后刷题时养成一个习惯写代码之前先把输入范围、空输入、全负、全正、单元素、多个解这六种情况想一遍。全正的时候算法退化成对整个数组求和全负的时候要按照题目约定处理单元素要区分正负多个解要看题目要求靠前还是靠后。还有一个容易被忽略的点多组输入。如果变量定义在while外面上一组数据留下的best和left会污染下一组的计算。把变量定义在while内部相当于每一组数据都从干净状态开始这是最省心的做法。这道题的数据量不大但养成在循环内初始化的习惯对以后处理复杂多组数据很有帮助。7. 个人心得与刷题建议7.1 第一次提交翻车记录我最初写这道题时把所有数当int样例过了数据一大就WA。检查半天发现不是溢出而是全负约定没处理。后来加allNegative又遇到区间左端点持续错误。老实说这道题简单在算法难在输出要求。总结一句话动态规划的状态定义决定正确性边界条件决定能不能过题。你可以在纸上先把状态转移方程写清楚再写代码。写完之后不要只跑样例要跑全负、有0、n1、多个解这几种情况。样例只能证明你“能跑通”不能证明你“想清楚了”。7.2 推荐练习路线与对拍方法建议练习顺序是先实现最大连续子序列和再加入记录首尾位置再改造成最大子矩阵再用线段树处理区间询问。每完成一个都写一个暴力函数做对拍。对拍其实很简单随机生成小规模数据暴力O(n^2)和DP同时跑比对结果。只要随机数据足够多大部分隐藏bug都会暴露。这个过程能培养你严谨读题和验证的习惯比看十篇题解都值。最后再分享一个小技巧。OJ上遇到WA先把输出规则逐字读一遍再检查所有边界如果输出都对还WA很可能是一个输出语句里的格式化符号用错了。纸上写代码时少犯这类错误实际敲代码也不能省。