1. 先把这两个问题放到正确的位置上动态规划学到序列这一层很多人会突然卡住。背包问题还能靠“背模板”混过去一遇到序列型 DP 就开始发懵状态到底该怎么定义转移为什么这么写换个题面又不会了。最大子段和与最长公共子序列这两个问题正好卡在这道坎上——它们不难但足够典型典型到把这两个吃透后面编辑距离、最长公共子串、最短公共超序列、环形数组最大和这一串题基本都能顺着同一条思路推下去。先说清楚它们各自解决什么。最大子段和处理的是单个序列上的连续区间问题给一串可能带负数的数字找出所有连续子段里和最大的那一个。它的关键词是“连续”而这个约束恰恰是很多人写不对的地方。最长公共子序列处理的是两个序列之间的匹配问题在两个字符串里各挑出若干个字符保持原有的先后顺序但不要求挨在一起问最多能挑出多少个相同的。它的关键词是“两个序列同时推进”这是一维 DP 迈入二维 DP 的第一道正式门槛。这两个问题覆盖的人群其实很广。刚刷完 01 背包、准备进阶序列 DP 的同学会觉得它们是最自然的下一站写过业务代码但说不清dp[i]到底代表什么的人能借它们把状态定义这件事真正想明白至于准备笔试面试的最大子段和的变形几乎年年出现LCS 更是被问烂了。我在实际带人和自己刷题的过程中发现能流利背出转移方程的人很多能解释清楚“为什么这个状态定义就能把连续约束吃掉”“为什么二维表要按这个方向填”的人少得多。这篇就按后一种标准来写。2. 最大子段和用状态定义吃掉“连续”这个约束2.1 问题定义里的三个边界必须先钉死题目本身很好懂给定长度 n 的整数序列 a[1..n]求形如 a[i] a[i1] ... a[j]1 ≤ i ≤ j ≤ n的所有子段中的最大和。但真动手写之前有三个边界必须先定下来否则代码写出来必然对不上测试点。第一个边界是子段能不能为空。这一点在算法题里表述往往是隐含的题目说“子段”通常意味着至少包含一个元素那么全负数序列的答案就是那个最大的负数。如果题目改口说“可以为空”或者“允许不选”那答案就是max(0, ...)。这两种约定在实战里都存在遇到题面模糊的时候我一般先按“至少一个元素”写然后回头核对样例看全负数的用例输出是负数还是 0。第二个边界是长度为一的序列。答案是 a[1] 本身这没什么争议但如果你用了“从第二个元素开始递推”的写法就必须单独处理 n 1不然会直接返回初始哨兵值。第三个边界是溢出的量级。n 到了 10 万、元素绝对值到 10^9总和就是 10^14 这个量级32 位整数直接爆掉。Python 不用担心C 里必须开long long。这个坑我在早年的一次线上评测里踩过一次本地小数据全过提交后一半用例挂掉排查了半天才发现是int累加溢出。2.2 状态定义是整个解法的核心最直接的暴力是枚举所有子段。三层循环枚举 i、j、k 是 O(n³)用前缀和把求和降成 O(1) 是 O(n²)。这两个版本在 n ≤ 5000 的时候还能活再大就不行了。真正把复杂度打到线性靠的是下面这个状态定义dp[i] 表示以 a[i] 结尾的所有子段中和最大的那一个的值。这个定义里最关键的两个字是“结尾”。很多人第一次看会觉得别扭我要求的是全局最大为什么状态只盯着以 i 结尾的原因在于“连续”这个约束让子段天然具备一个漂亮的递推性质——以 a[i] 结尾的子段要么就是 a[i] 自己单独成一个段要么就是把 a[i] 接在某个以 a[i-1] 结尾的子段后面。没有第三种可能。这个性质叫做最优子结构在连续约束下的特殊表现。正因为只有这两种接法我们才不需要知道前面那个子段的起点在哪只要知道它最大的和是多少就够了。dp[i-1]恰好携带了这个信息其他的历史细节对于求最大值而言全都无关紧要这就是所谓的无后效性。2.3 转移方程是怎么推出来的顺着上面的分类讨论转移方程几乎是自动落地的dp[i] max(dp[i-1] a[i], a[i])含义非常直白。如果前面的累积值是正的接上 a[i] 只会更大那就接上如果前面的累积值已经是负的接上去纯属拖后腿那还不如从 a[i] 重新开始一段。至于相等的情况接不接都不影响数值本身但会影响起止下标这个差异在需要输出区间时才有意义。最终的答案不是dp[n]而是max(dp[1], dp[2], ..., dp[n])。这一点特别容易错——因为状态定义锁死了“以 i 结尾”而全局最优子段未必结束在最后一个位置。我见过不止一个人写成返回dp[n]然后在样例上翻车。拿序列[-2, 1, -3, 4, -1, 2, 1, -5, 4]手算一遍过程是这样的下标 ia[i]dp[i-1] a[i]a[i]dp[i]当前最优1-2--2-2-221-11113-3-2-3-214424445-13-1346252557161668-51-516945456结果是 6对应子段[4, -1, 2, 1]。注意在第 8 步dp[7] a[8] 6 - 5 1比 a[8] 本身大所以没有重置但也没有超过历史最优。这种“累积值还是正的所以继续接但整体已经被历史最优甩开”的情况是手算时最容易看走眼的地方。2.4 空间压缩与起止下标的还原观察转移方程dp[i]只依赖dp[i-1]整个数组根本不用存。用一个变量滚动就够了空间从 O(n) 降到 O(1)def max_subarray(a): best cur a[0] for x in a[1:]: cur max(cur x, x) best max(best, cur) return best这段代码只有五行但里面每一行都有讲究。best cur a[0]同时初始化两个变量是为了让全负数序列也能正确返回第一个元素。循环从a[1:]开始是因为a[0]已经被吃进初始值了。如果写成best 0全负数就返回 0那就是另一种题意了。需要输出起止下标的时候稍微改一下结构def max_subarray_range(a): best cur a[0] l r start 0 for i in range(1, len(a)): if cur 0: cur a[i] start i else: cur a[i] if cur best: best cur l, r start, i return best, l, r这里的start变量记录当前这段的起点只有在“重置”发生时才更新。判定条件用cur 0而不是cur 0是因为当累积值恰好等于 0 时接上后面的元素不会变差保留更长的区间通常更符合题目对“输出任意一个最优解”的宽容度。不过如果题目明确要求输出最短的那个最优区间这里就得反过来写成cur 0。提示这两种写法在只求数值时完全等价只有在需要还原区间、并且存在多个最优解时才会产生差异。做题前先看清楚题目对多解的要求。2.5 分治解法和线段树扩展线性解法已经足够优了但最大子段和还有一个同样经典的 O(n log n) 分治写法值得了解因为它能推广到线段树的区间查询场景。分治的思路是把区间从中间切开最优子段要么完全落在左半要么完全落在右半要么跨越中点。前两种递归求解第三种可以用“从中点向左的最大后缀和”加上“从中点向右的最大前缀和”拼出来def max_sub_dc(a, l, r): if l r: return a[l] mid (l r) // 2 left max_sub_dc(a, l, mid) right max_sub_dc(a, mid 1, r) s, best_l 0, float(-inf) for i in range(mid, l - 1, -1): s a[i] if s best_l: best_l s s, best_r 0, float(-inf) for i in range(mid 1, r 1): s a[i] if s best_r: best_r s return max(left, right, best_l best_r)跨中点的那部分是 O(n)整体递推式 T(n) 2T(n/2) O(n)解出来就是 O(n log n)。这个写法的价值不在于它更快其实更慢而在于每个区间只需要维护四个量就能合并区间总和、最大前缀和、最大后缀和、最大子段和。这四个量满足可合并性于是可以架到线段树上支持“单点修改 区间最大子段和查询”复杂度 O(log n)。某些带修改的题目就是靠这一手做的。我第一次从线性写法切到线段树写法时最大的感受是同一个问题换一种状态定义能支持的查询类型完全不一样这才是动态规划真正有意思的地方。3. 最长公共子序列二维表是怎么被填出来的3.1 子序列和子串差的不是一个字进入正题之前必须先把这个区别说清楚因为它是 LCS 类问题里错误率的头号来源。子串要求字符在原串里连续出现abc的子串包括ab、bc、abc但不包括ac。子序列只要求保持相对顺序允许跳过中间字符abc的子序列包括ac、bc、abc甚至单个字符。这两个概念在代码上只差一个转移分支子串问题在字符不匹配时直接把dp归零重新开始子序列问题则是从上方或左方继承最优值。但题目类型、难度、常见套路完全不同读题时看到“substring”“连续”就要反应过来是子串看到“subsequence”“不要求连续”就是子序列。LCS 的完整定义是给定两个序列 X长度 n和 Y长度 m求一个最长的序列 Z使得 Z 同时是 X 和 Y 的子序列。注意 Z 不需要唯一很多情况下存在多条长度相同的最长公共子序列题目一般只问长度。拿一个具体例子铺开X ABCBDABY BDCABA最长公共子序列之一是BCBA长度为 4。你可以自己对着两个串验证一下B、C、B、A在 X 里出现的次序是 1、3、4、6在 Y 里是 1、3、4、6顺序完全对得上。3.2 状态定义与转移的两种情形一维状态搞不定这个问题因为同时有两个序列在推进必须用二维dp[i][j] 表示 X 的前 i 个字符和 Y 的前 j 个字符的最长公共子序列长度。接下来按“X 的第 i 个字符和 Y 的第 j 个字符是否相等”分类讨论这是整个推导的骨架。情形一X[i] Y[j]。这两个字符可以直接配对放在公共子序列的末尾然后剩下的问题就变成了 X 前 i-1 个字符和 Y 前 j-1 个字符的 LCS。于是dp[i][j] dp[i-1][j-1] 1这里有个容易被忽略的细节为什么不用考虑“不配对”的情况直觉上即使两个字符相等我们也可以选择不把它们配对去谋求更大的长度。但实际上如果 X[i] Y[j]那么把它们配对一定不会比不配对差。这个结论可以用反证说明设存在一个最优解不配对这两个字符那么把这两个字符附加到该解的末尾得到的仍然是合法的公共子序列长度还增加了 1矛盾。所以配对是安全的选择。这个“贪心性质”是 LCS 转移成立的前提值得单独想一遍。情形二X[i] ! Y[j]。这两个字符不可能同时出现在公共子序列的同一个位置上所以至少有一个用不上。要么放弃 X[i]在dp[i-1][j]里找要么放弃 Y[j]在dp[i][j-1]里找。取两者较大值dp[i][j] max(dp[i-1][j], dp[i][j-1])写代码之前还有一件事dp[i-1][j-1]这一项用不用考虑答案是不用。因为dp[i-1][j] ≥ dp[i-1][j-1]且dp[i][j-1] ≥ dp[i-1][j-1]长度单调不减它已经被包含在 max 里了。我第一次推导时习惯性写成三项取 max结果发现不影响正确性但多了一次无谓的比较。3.3 边界、填表方向和滚动数组边界条件很简单dp[0][j] 0X 为空串时 LCS 长度为 0dp[i][0] 0Y 为空串时同理。所以二维数组一般开成(n1) × (m1)多出来的一行一列专门放边界。填表的顺序必须保证算dp[i][j]时它的左上、上方、左方三个格子都已经算好。满足这个条件的遍历方式是从 i 1 到 n内层 j 1 到 m也就是逐行从左到右填。反过来先遍历 j 再遍历 i 也行只要内外层的方向一致就行。def lcs_len_table(s, t): n, m len(s), len(t) dp [[0] * (m 1) for _ in range(n 1)] for i in range(1, n 1): si s[i - 1] row, prev dp[i], dp[i - 1] for j in range(1, m 1): if si t[j - 1]: row[j] prev[j - 1] 1 else: row[j] prev[j] if prev[j] row[j - 1] else row[j - 1] return dp[n][m]完整二维表的时间和空间都是 O(nm)。当 n 和 m 都到 5000 时25 × 10^6 个 int 在 Python 里是很吃内存的Python 的 list of list 每个 int 还是对象引用开销比 C 大得多。这时候需要滚动数组优化def lcs_len_rolling(s, t): if len(s) len(t): s, t t, s m len(t) prev [0] * (m 1) for i in range(1, len(s) 1): cur [0] * (m 1) si s[i - 1] for j in range(1, m 1): if si t[j - 1]: cur[j] prev[j - 1] 1 else: cur[j] prev[j] if prev[j] cur[j - 1] else cur[j - 1] prev cur return prev[m]空间降到 O(min(n, m))时间不变。注意开头那两行交换滚动数组的长度应该取两个串中较短的那个这样能省下不少内存。这是个几乎零成本的小优化但很多人写的时候顺手就把外层设成第一个串不做判断。注意滚动数组里的cur[j]依赖同一行的cur[j - 1]所以内层循环必须从左往右。如果写成从右往左cur[j-1]还是上一行的旧值答案直接错。这个错误极其隐蔽因为小数据上未必能暴露出来。滚动数组能求长度但没法回溯出具体的公共子序列因为历史行已经被覆盖了。要输出方案要么老老实实存整张表要么用 Hirschberg 分治算法O(min(n,m)) 空间 O(nm) 时间。后者的思路是先算出中间行各位置的前缀 LCS 长度再从后往前算后缀 LCS 长度找到总长最大的分割点把问题切成两个子问题递归处理。这个算法思路很漂亮但代码量不小一般只在内存受限的场合才用得上。3.4 回溯出一条具体的公共子序列面试里更常见的要求是“打印一条最长公共子序列”这时候老老实实开二维表最省事。回溯的逻辑就是从dp[n][m]出发往左上走def lcs_string(s, t): n, m len(s), len(t) dp [[0] * (m 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, m 1): if s[i - 1] t[j - 1]: dp[i][j] dp[i - 1][j - 1] 1 else: dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) i, j, res n, m, [] while i 0 and j 0: if s[i - 1] t[j - 1]: res.append(s[i - 1]) i - 1 j - 1 elif dp[i - 1][j] dp[i][j - 1]: i - 1 else: j - 1 return .join(reversed(res))回溯的三个分支对应三种走法字符相等时收录这个字符并走左上否则朝数值更大的那个方向走。如果上方和左方相等随便选一个都行但只选一个——有些实现里写成两个分支都走就变成搜索所有解了复杂度会飙升。想让输出的序列在多个解之间保持稳定比如字典序最小的那个就需要在dp[i-1][j] dp[i][j-1]时做一个额外的比较决策这也是某些题目追加的成环要求。实际工程里diff之类的工具就是在 LCS 的基础上加了权值和启发式规则让它更符合人的阅读习惯。3.5 洛谷最长公共子序列排列场景的降维打击上面这套 O(nm) 的做法并不是万能的。有一个非常经典的题目——两个长度都为 n 的排列求 LCS——直接套二维表在 n 10^5 时必然超时超内存必须换思路。关键在于排列这个特殊条件两个序列里的元素集合完全相同每个数字恰好出现一次。那么可以把第一个序列里的每个值映射成它的下标位置然后拿第二个序列按这个映射转换成一串下标。这样一来第二个序列的一个上升子序列就对应着两个序列的一个公共子序列问题从 LCS 转化成了最长上升子序列LIS而 LIS 有 O(n log n) 的贪心 二分做法。import sys, bisect def solve(): data sys.stdin.buffer.read().split() n int(data[0]) a list(map(int, data[1:1 n])) b list(map(int, data[1 n:1 2 * n])) pos [0] * (n 1) for idx, v in enumerate(a): pos[v] idx tails [] for v in b: x pos[v] k bisect.bisect_left(tails, x) if k len(tails): tails.append(x) else: tails[k] x print(len(tails)) solve()这里的tails数组维护的是“长度为 k1 的上升子序列的最小结尾元素”用bisect_left保证是严格上升如果题目允许非下降子序列就换成bisect_right。整个算法 O(n log n)10^5 的数据毫无压力。我第一次看到这个转化时是有点震撼的因为它说明了一件事很多看似需要 O(nm) 的问题一旦看出输入结构的特殊性就能降维。做题时先看数据范围再看题目对输入的特殊限制这个习惯比记住十道题的模板更有用。4. 实操复盘复杂度算账和可复现的完整代码4.1 不同数据规模该选哪种写法写代码之前先看数据范围这是我个人最看重的一条工程习惯。把两个问题的各种写法整理成一张对照表问题写法时间复杂度空间复杂度适用规模Python最大子段和三层暴力O(n³)O(1)n ≤ 100最大子段和前缀和枚举O(n²)O(n)n ≤ 5000最大子段和线性 DPO(n)O(1)n ≤ 10^7最大子段和分治O(n log n)O(log n)n ≤ 10^6LCS完整二维表O(nm)O(nm)n, m ≤ 2000LCS滚动数组O(nm)O(min(n,m))n, m ≤ 5000LCS排列转 LISO(n log n)O(n)n ≤ 10^6有个细节要补一下Python 里的二维 int 列表内存开销远大于 C同样是 2000 × 2000 的表C 用short只要 8MBPython 可能要 60MB 以上。所以 Python 选手的临界规模要比表里 C 的经验值再往下压一压。真到了顶不住的时候可以考虑用array模块或者numpy存表能省下大量内存。4.2 输入输出的常数问题这两个问题在评测平台上经常卡常数。以最大子段和为例n 10^6 时读入本身就是瓶颈。sys.stdin.buffer.read().split()比逐行input()快一个数量级这个差距在 Python 上非常明显。我做过一个粗糙的实测读取 100 万个数逐行input()加int()大约要 1.2 秒而一次性read().split()加map(int, ...)大概 0.25 秒。前者在时限 1 秒的题上直接出局。输出也一样频繁print会拖慢程序数量大的时候统一收集到一个列表里再\n.join(...)输出。另一个常被忽略的点是内层循环里不要做函数调用。LCS 的转移写成max(prev[j], cur[j-1])和写成三元表达式在 5000 × 5000 的规模下Python 上能差出百分之二十几。原因是max是函数调用有额外的栈帧开销。这个优化在 C 里基本无所谓编译器会内联但在 Python 里值得留意。4.3 一份可以直接跑的完整测试脚本把两个问题的核心实现串起来加一个随机对拍方便验证自己的理解import random def max_sub_dp(a): best cur a[0] for x in a[1:]: cur x if cur 0 else cur x if cur best: best cur return best def max_sub_brute(a): n len(a) ans a[0] for i in range(n): s 0 for j in range(i, n): s a[j] if s ans: ans s return ans def lcs_dp(s, t): n, m len(s), len(t) prev [0] * (m 1) for i in range(1, n 1): cur [0] * (m 1) for j in range(1, m 1): if s[i - 1] t[j - 1]: cur[j] prev[j - 1] 1 else: cur[j] prev[j] if prev[j] cur[j - 1] else cur[j - 1] prev cur return prev[m] def lcs_brute(s, t): from functools import lru_cache lru_cache(maxsizeNone) def go(i, j): if i 0 or j 0: return 0 if s[i - 1] t[j - 1]: return go(i - 1, j - 1) 1 return max(go(i - 1, j), go(i, j - 1)) return go(len(s), len(t)) random.seed(20240501) for _ in range(500): arr [random.randint(-20, 20) for _ in range(random.randint(1, 12))] assert max_sub_dp(arr) max_sub_brute(arr), arr alpha abcd for _ in range(300): s .join(random.choice(alpha) for _ in range(random.randint(0, 8))) t .join(random.choice(alpha) for _ in range(random.randint(0, 8))) assert lcs_dp(s, t) lcs_brute(s, t), (s, t) print(all passed)对拍的思路就是用一份慢但绝对正确的暴力实现当基准随机造大量小数据互相比对。这套方法在两个问题上都特别有效因为它们的暴力版本很容易写对而优化版本的边界容易出岔子。我个人的习惯是任何 DP 实现不管多自信都先跟暴力对拍到 500 组小数据再提交能挡掉八成的低级错误。提示对拍时随机数的范围要小比如元素控制在 [-20, 20]字符串字母表控制在 2 到 4 个字符。范围太大反而不容易撞出边界情况比如全负数、两个串完全不相交、其中一个是空串这些。5. 踩坑记录与常见问题速查5.1 最大子段和最容易翻车的几个地方返回了dp[n]而不是历史最大值。这是出现频率最高的错误。状态定义是“以 i 结尾”那全局答案自然要单独维护一个best变量。修法很简单但思想上要转过弯状态值不等于答案值这个问题上体现得最典型。初始值设成 0 导致全负数序列返回 0。如果题意要求子段非空答案必须是最大的那个负数设成 0 就错了。正确的做法是用序列的第一个元素初始化best和cur。用 32 位整数累加。前面提过n 大、元素大的时候必然溢出。C 里long long是标配别省。重置条件的等号方向搞反。cur 0才重置写成cur 0在只求数值时结果一样但会影响还原出来的区间。需要输出区间的时候要看清楚题目要求。环形数组直接用线性解法。有一类变形题目把序列首尾相接成环问最大子段和。正确的做法是取两种情况的最大值不跨越边界的最大子段和以及总和减去最小子段和。但最后一步有个坑——如果序列全是负数第二种情况会算出空段此时必须直接返回第一种情况的结果def max_sub_circular(a): total sum(a) best max_sub_dp(a) if best 0: return best neg [-x for x in a] return max(best, total max_sub_dp(neg))这里把求最小子段和巧妙地转成了求相反数的最大子段和省得再写一遍逻辑。注意total max_sub_dp(neg)这个写法因为最小子段和等于负的最大子段和。5.2 LCS 身上的雷区把子序列当成子串。前面说过判定分支不一样。子序列问题在不匹配时取max(dp[i-1][j], dp[i][j-1])子串问题在不匹配时直接归零。这两类题的代码看起来像结果差得远。滚动数组的遍历方向写反。从左到右必须从左到右。想清楚cur[j]依赖cur[j-1]这一点就不会错。滚动数组还想还原方案。做不到。求长度可以滚求具体序列必须存整表或者上 Hirschberg。我第一次被人问到“滚动数组怎么回溯”时卡了半天后来才意识到这是个不可能任务。二维表开小了。习惯性开成n × m而不是(n1) × (m1)然后在处理dp[0][j]时越界。多开一行一列当作空串边界是这类问题的标准姿势。递归记忆化写法爆栈。用lru_cache写递归版本读起来很清爽但 n、m 上到几千时 Python 的递归深度限制会直接报错。生产代码里还是老老实实写迭代。以为 LCS 一定唯一。大多数情况下不唯一题目一般只要求长度。要求输出具体序列时通常允许输出任意一个合法解除非题目额外规定了字典序等约束。5.3 问题速查表现象可能原因排查方向全负数用例输出 0初始值设成了 0用首元素初始化最大子段和答案偏小返回了dp[n]单独维护历史最大值LCS 结果比预期大把子串当子序列做了检查不匹配分支LCS 结果比预期小滚动数组遍历方向反了内层改回从左往右程序内存超限二维表未压缩换滚动数组或转 LIS大数组运行超时读入方式太慢换buffer.read().split()排列类 LCS 超时未识别出可转 LIS 的结构检查两序列元素集合是否相同递归版本崩溃递归深度超限改写成迭代版写到这里从最大子段和的状态定义是怎么把连续约束吃掉到 LCS 的二维表为什么按行填、怎么回溯、排列场景怎么降维成 LIS这条线索基本铺完了。我个人的体会是这两道题真正的价值不在解法本身而在于它们分别代表了两种状态设计的思路一个用“以 i 结尾”把区间约束压缩进单点一个用两个维度分别跟踪两个序列的进度。以后再遇到“区间最优”“两个序列匹配”这类题面先往这两个模板上靠一靠往往能找到突破口。至于那份随机对拍脚本建议真的跑一遍再动手改代码比看十遍推导都管用。