企业官网建设流程全解析

动态规划这块，最大子段和和最长公共子序列基本是绕不开的两道坎。前者是一维线性DP的入门样板，后者是二维序列DP的教科书样本，几乎所有讲到动态规划（DP）的课程都会把它们拎出来单独说一遍。我这些年刷题、带人、写题解，发现一个规律：能把这两道题从头到尾讲清楚的人，后面学区间DP、树形DP、状态压缩都会顺很多；反过来，这两道题里含糊过去的坑，会在后面反复以各种形态冒出来。这篇就按我自己的理解路径，把这两道题从"为什么这么定义状态"到"代码怎么写、怎么调、怎么优化"完整拆一遍，中间会穿插我实测过的多种写法和踩过的坑。适合刚学完递归和基础枚举、准备进入DP的读者，也适合写了很久但一直靠"背模板"过题、想重新把底层逻辑理顺的读者。

1. 先想清楚这两个问题为什么值得单独拎出来讲

1.1 状态定义的颗粒度，直接决定你后面写多少行代码

很多人学DP卡住的地方，不是不会写循环，而是不知道该把"状态"定义成什么。最大子段和和最长公共子序列恰好是两种典型的颗粒度示范。

最大子段和的状态是"以第 i 个元素结尾的最大子段和"，注意这个"以 i 结尾"四个字极其关键。如果定义成"前 i 个元素里的最大子段和"，转移方程就写不出来，因为你不知道新加进来的元素能不能接上前面那段。加上"以 i 结尾"这个限定，最后一个元素就被钉死了，剩下的选择只有两个：接上前面的段，或者自己另起一段。这就是典型的"用限制换转移可行性"。

最长公共子序列的状态是"a 的前 i 个字符和 b 的前 j 个字符的最长公共子序列长度"。注意这里用的是"前 i 个"，因为两个字串之间没有"最后一个必须匹配"这种强制约束，长度本身就是我们要的答案，所以可以直接用前缀。

这两种颗粒度没有优劣，取决于题目问的是什么。翻译成一句可以复用的经验：如果答案是"最优值"而不是"某个位置的局部最优值"，通常可以用前缀状态；如果转移需要依赖"上一个被选中的元素是谁"，就得把位置信息塞进状态里。

1.2 两个模型其实是同一套骨架的两种变体

把这两道题的代码摆在一起看，你会发现骨架惊人地一致：定义状态、写转移、定初值、定遍历顺序、定答案位置。区别只在于最大子段和的转移是"线性的一前一后"，LCS 的转移是"二维的左、上、左上"。

我用一张表把这两道题的骨架并排放一下，方便对照：

这张表里最容易被忽略的是"答案位置"那一行。最大子段和的答案不在 dp[n-1]，而在所有 dp[i] 里的最大值，这个点后面会专门展开讲，因为它是新手最容易错的地方之一。

1.3 动手写之前先确认三件事

在敲代码之前，我现在的习惯是先在纸上确认三件事，确认完再动手，能省掉大量调试时间。

第一件事是边界语义。最大子段和里，"子段"到底允不允许为空？如果允许空，全负数数组的答案是 0；如果不允许空，答案是最大的那个负数。这两种定义在题目里都出现过，读题时必须抠清楚。LCS 里，空串算不算公共子序列？算，所以 dp[0][j] 和 dp[i][0] 全部为 0，这个基本没有歧义。

第二件事是下标体系。是 0-based 还是 1-based？我强烈建议 DP 表的行列下标从 1 开始，把第 0 行和第 0 列留给空串或空段，代码里写 dp[i-1][j-1] 的时候不容易搞混。代价是访问原数组要写 a[i-1]，但这笔账很划算。

第三件事是数据规模。最大子段和如果是 n ≤ 2×10^5，那只能 O(n) 或 O(n log n)；LCS 如果 n、m 都在 10^3 量级，O(nm) 完全够，但如果题目给的是两个排列、n 到 10^5，那 O(nm) 必爆，得换思路。规模决定算法选型，这一步偷懒，后面重写的时间成本更高。

注意：别一上来就套记忆里的模板。先花两分钟确认这三件事，比写完发现题意理解错了再推倒重来要快得多。

2. 最大子段和：从三层循环到一次遍历的瘦身过程

2.1 先把题目边界抠干净：非空还是可空

最大子段和的标准表述是：给一个整数序列，找出一个连续的子段，使它的和最大。这里"连续"是硬约束，"子段"至少包含一个元素是常见约定（也就是非空）。

非空带来的最直接后果是：如果数组全是负数，答案是其中最大的那个负数，而不是 0。这个结论看起来很朴素，但实际写代码时特别容易翻车，因为很多人脑子里默认"不选就是 0"。

还有一种变体是"允许空段"，这时候全负数数组答案就是 0。判断方法很简单，看题目描述里有没有"可以为空"或"至少包含一个数"。如果没有明确说，默认非空。

我踩过一次典型的坑：某道题我按允许空段的思路写了ans = max(0, ...)，结果全负数测试点直接错。后来养成习惯，函数命名上直接把语义写出来，比如max_subarray_nonempty，这样调用的时候不会记混。

2.2 状态定义是怎么一步步想出来的

先用最笨的办法想：枚举左端点 l 和右端点 r，把中间加起来。这是 O(n^3)，n 到 100 就跑不动了。第一步优化，预处理好前缀和，区间和变成 O(1)，整体降到 O(n^2)。n 到 5000 勉强能过，再大就不行了。

想再降，就得换个角度：不要枚举区间，而是从左往右"扫"过去，边扫边维护一些信息。

扫到第 i 个元素时，考虑所有"以 i 结尾"的子段。这些子段分成两类：只有 a[i] 一个元素的，和"以 i-1 结尾的某个子段再接上 a[i]"。要让第二类和最大，显然应该挑"以 i-1 结尾的最大子段和"来接。于是状态就定出来了：

dp[i] = 以 a[i] 结尾的最大子段和

转移方程随之而来：

dp[i] = max(a[i], dp[i-1] + a[i])

初值是dp[0] = a[0]。最终答案是max(dp[0..n-1])，因为最大子段可能以任何一个位置结尾，不是必须以最后一个元素结尾。

这个推导过程里有一个隐含前提：如果 dp[i-1] 是负数，那么接上它只会拖后腿，不如另起一段。这一步就是整个算法的灵魂，也是很多人"知道代码但讲不出为什么"的地方。

2.3 三版代码对照与实测

我把三个版本都写出来，你可以直接跑，感受一下差距。

第一版，纯暴力枚举加求和：

def max_subarray_brute(a): n = len(a) best = a[0] for i in range(n): for j in range(i, n): s = sum(a[i:j+1]) # 每次重新求和，浪费 best = max(best, s) return best

这段代码在 n = 200 时大约要跑几十万次加法，n 到 1000 就明显卡了。

第二版，前缀和优化：

def max_subarray_prefix(a): n = len(a) pre = [0] * (n + 1) for i in range(n): pre[i + 1] = pre[i] + a[i] best = a[0] for i in range(n): for j in range(i + 1, n + 1): best = max(best, pre[j] - pre[i]) return best

这里语义上更接近"枚举左端点 i，再枚举右端点 j"，只是区间和用前缀和查表。复杂度 O(n^2)。

第三版，Kadane 算法，也就是标准解：

def max_subarray(a): cur = best = a[0] for x in a[1:]: cur = max(cur + x, x) # 接上还是另起 best = max(best, cur) return best

这里cur就是滚动后的 dp[i]，best就是全局答案。整个循环只做两次比较和一次加法，n = 10^6 也就几十毫秒的事。

我第一次从 O(n^2) 改成 O(n) 的时候，心里是有怀疑的：这么简单的循环真的对吗？后来自己手动跑了几组数据，包括全负数、单元素、交替正负这些情况，才彻底服气。手动模拟一遍的过程强烈建议你也做一次，尤其是记录每一步的 cur 和 best 变化，比看十遍题解管用。

2.4 滚动变量的空间压缩

dp 数组其实完全不需要。观察转移方程，dp[i] 只依赖 dp[i-1]，前面所有值都用不上了。所以用一个变量cur滚动就行，空间从 O(n) 降到 O(1)。

这里有个细节值得说：虽然我们只保留了最新的 dp 值，但"答案"不能跟着滚动掉，因为最大子段不一定以最后一个元素结尾。所以必须单独用一个best变量实时更新。很多人压缩空间的时候顺手把 best 也搞没了，最后返回 cur，那就错了。

如果题目还要求输出这个子段本身（起点和终点下标），那就不能只滚一个值了，得一边更新一边记录起点。常见的做法是：当cur + x < x时，说明另起一段，此时把起点更新为 i；每当 best 被刷新，就把当前起点和 i 存进结果变量。

def max_subarray_with_index(a): cur = best = a[0] start = cur_start = 0 end = 0 for i in range(1, len(a)): if cur + a[i] < a[i]: cur = a[i] cur_start = i else: cur += a[i] if cur > best: best = cur start, end = cur_start, i return best, start, end

这段代码我在面试里被问到过两次，考的就是"空间压缩的同时还能不能还原方案"。

2.5 环形与二维扩展：同一套思想换皮

把数组首尾接起来变成环，问最大子段和，这是很经典的一道变体。思路分两种情况。

第一种，答案子段没有跨越首尾，那就是普通的线性最大子段和。第二种，答案子段跨越了首尾，那么它相当于"整个数组的和，减去中间那段连续的最小子段和"。因为跨越首尾的部分 = 总和 - 中间挖掉的部分，要让结果最大，就要让挖掉的部分最小。

代码大概是这样：

def max_subarray_circular(a): total = sum(a) best = max_subarray(a) # 非空最大子段和 if best < 0: return best # 全负数，环形也只能取单个元素 cur_min = mn = a[0] for x in a[1:]: cur_min = min(cur_min + x, x) mn = min(mn, cur_min) return max(best, total - mn)

那个if best < 0的判断就是前面说的"非空"带来的坑。如果全是负数，total - mn 会等于 0，对应"什么都不取"，但题目要求非空，所以必须特判掉。

再往二维推，就是最大子矩阵和。做法是枚举行的上下边界 top 和 bottom，把这一段的每一列求和压成一个一维数组，然后跑一次 Kadane。复杂度 O(n^2 * m)，n、m 都在几百的时候可以接受。

def max_submatrix(mat): n, m = len(mat), len(mat[0]) best = -10**18 for top in range(n): col = [0] * m for bottom in range(top, n): for k in range(m): col[k] += mat[bottom][k] best = max(best, max_subarray(col)) return best

这里的核心思想是降维：把二维问题在某一维上枚举掉，剩下的维度压成一维。这个套路后面在状态压缩DP里还会反复出现。

3. 最长公共子序列：二维DP的经典样本

3.1 子序列和子串，一字之差天壤之别

先把概念钉死。子序列是从原串里删掉若干字符（可以一个都不删）后剩下的、保持原有相对顺序的序列，不要求连续。子串是必须连续的一段。

举例子，"abcde" 和 "ace" 的公共子序列，但 "ace" 不是 "abcde" 的子串。"abcde" 和 "bc" 的关系里，"bc" 两者都算。

这个区别直接决定状态转移。求最长公共子序列时，字符 a[i-1] 和 b[j-1] 不相等，我们还能"跳过"其中一个继续往前比；求最长公共子串时，一旦不相等，当前这一段就断了，必须清零重来。

很多新手写 LCS 时把else分支写成dp[i][j] = 0，那就变成求最长公共子串了，题目要求一变，答案直接差一大截。这个错误我在帮人看代码时见过不下十次。

3.2 dp[i][j] 的语义与转移推导

状态定义：dp[i][j]表示字符串 a 的前 i 个字符和字符串 b 的前 j 个字符的最长公共子序列长度。

推导按 a[i-1] 和 b[j-1] 是否相等分两路。

如果相等，这两个字符可以直接配成一对，放在公共子序列的末尾，那么长度就是dp[i-1][j-1] + 1。这里有个常见疑问：凭什么相等就一定配上？会不会不配上反而更长？答案是不会，因为配上之后新增的这个字符在最末尾，不影响前面的任何选择，属于"白赚一个"。

如果不相等，那么 a[i-1] 和 b[j-1] 至少有一个不在最终的公共子序列里。于是考虑三种情况：a[i-1] 不参与，答案取 dp[i-1][j]；b[j-1] 不参与，答案取 dp[i][j-1]；两个都不参与，答案取 dp[i-1][j-1]。第三种情况被前两种包含（因为 dp 值单调不减），所以只需要取前两个的最大值。

转移方程：

dp[i][j] = dp[i-1][j-1] + 1 若 a[i-1] == b[j-1] dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 否则

初值：dp[0][j] = dp[i][0] = 0，对应空串和任何串的公共子序列长度都是 0。

答案是dp[n][m]。注意这里和最大子段和不同，LCS 的答案就在右下角，因为我们要的本来就是"两个完整串"的结果。

3.3 代码实现与路径回溯

基础版：

def lcs_length(a, b): n, m = len(a), len(b) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) return dp[n][m]

如果题目要求输出具体的那个公共子序列，就得从 dp[n][m] 往回走。规则是：如果 a[i-1] == b[j-1]，这个字符属于答案，记录它，然后 i 和 j 同时减一；否则比较 dp[i-1][j] 和 dp[i][j-1]，往大的那边走。

def lcs_path(a, b): n, m = len(a), len(b) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) res = [] i, j = n, m while i > 0 and j > 0: if a[i-1] == b[j-1]: res.append(a[i-1]) i -= 1 j -= 1 elif dp[i-1][j] >= dp[i][j-1]: i -= 1 else: j -= 1 return dp[n][m], ''.join(reversed(res))

回溯时那个>=和>的取舍，会决定当两条路径长度相同时走哪条。两种都能得到合法答案，但如果不小心写成<=并配错方向，就可能出现死循环或者长度对不上。我个人的习惯是统一往"上"优先，即dp[i-1][j] >= dp[i][j-1]时让 i 减一，这样得到的解更稳定，方便对拍。

3.4 滚动数组优化的正确姿势

二维 dp 表在 n、m 都到 5000 的时候就是 2500 万个格子，即使存 short 也要几十 MB，很多题的内存限制扛不住。优化思路是用两行滚动，更进一步压成一行加一个变量。

观察转移：dp[i][j] 只依赖 dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]。这三个分别对应"左上、上、左"。用一行数组row，在更新 row[j] 之前，row[j] 存的是上一行的 dp[i-1][j]（"上"），row[j-1] 已经被更新成 dp[i][j-1]（"左"），而"左上"那个值会被 row[j] 覆盖掉，所以必须用临时变量提前存起来。

def lcs_rolling(a, b): n, m = len(a), len(b) row = [0] * (m + 1) for i in range(1, n + 1): prev = 0 # 相当于 dp[i-1][0] for j in range(1, m + 1): tmp = row[j] # 保存 dp[i-1][j] if a[i-1] == b[j-1]: row[j] = prev + 1 else: row[j] = max(row[j], row[j-1]) prev = tmp # 给下一列当"左上" return row[m]

这段代码我第一次写的时候错了两次。第一次忘了更新 prev，第二次把 prev 的赋值放在了 if 之前，导致匹配分支拿到的不是 dp[i-1][j-1]。后来我养成了一个习惯：在代码旁边手写一遍三个角色的对应关系（上 = row[j] 旧值，左 = row[j-1] 新值，左上 = prev），对照着敲，基本一次就对。

注意：滚动数组省了空间，但丢掉了完整的 dp 表，也就没法回溯路径了。如果题目要求输出具体方案，要么保留完整表，要么另用别的方式记录决策。

3.5 相邻变体：最长公共子串与编辑距离

最长公共子串的转移稍有不同：相等时dp[i][j] = dp[i-1][j-1] + 1，不相等时直接归零。答案是所有 dp[i][j] 里的最大值，而不是右下角。这一点和最大子段和一样，属于"答案在全局"的类型。

def longest_common_substring(a, b): n, m = len(a), len(b) dp = [[0] * (m + 1) for _ in range(n + 1)] best = 0 for i in range(1, n + 1): for j in range(1, m + 1): if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1 best = max(best, dp[i][j]) return best

编辑距离又是同一族里的另一个成员，转移是三种操作的取最小值：

def edit_distance(a, b): n, m = len(a), len(b) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(n + 1): dp[i][0] = i for j in range(m + 1): dp[0][j] = j for i in range(1, n + 1): for j in range(1, m + 1): cost = 0 if a[i-1] == b[j-1] else 1 dp[i][j] = min( dp[i-1][j-1] + cost, # 替换 dp[i-1][j] + 1, # 删除 dp[i][j-1] + 1 # 插入 ) return dp[n][m]

把这三个放在一起看，你会发现二维序列DP的基本套路就是：在 (i-1, j)、(i, j-1)、(i-1, j-1) 这三个格子里做文章，具体怎么组合，取决于题目允许什么操作、问的是什么。

4. 完整落地：两道题的实测与调试记录

4.1 最大子段和整套代码与用例

我平时写这类函数，会顺手带一段自测，把边界情况全覆盖上。

def max_subarray(a): cur = best = a[0] for x in a[1:]: cur = max(cur + x, x) best = max(best, cur) return best if __name__ == '__main__': cases = [ ([1, -2, 3, 10, -4, 7, 2, -5], 18), ([-2, -1, -3], -1), ([5], 5), ([0, -1, 2, -3, 4], 4), ([-1, 0, -2], 0), ] for arr, expect in cases: got = max_subarray(arr) print(arr, 'got', got, 'expect', expect, 'OK' if got == expect else 'FAIL')

第二组[-2, -1, -3]就是专门用来打"非空"这个点的，答案是 -1 而不是 0。第五组[-1, 0, -2]是混合了 0 的情况，答案是 0，因为单独取那个 0 就是合法子段。

这几组数据看着简单，但它们覆盖了：全正、全负、含零、单元素、正负交替。我建议任何人写完这个函数都拿这几组跑一遍，比随手造数据靠谱。

4.2 LCS整套代码与用例

def lcs_path(a, b): n, m = len(a), len(b) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(1, m + 1): if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) res = [] i, j = n, m while i > 0 and j > 0: if a[i-1] == b[j-1]: res.append(a[i-1]); i -= 1; j -= 1 elif dp[i-1][j] >= dp[i][j-1]: i -= 1 else: j -= 1 return dp[n][m], ''.join(reversed(res)) if __name__ == '__main__': tests = [ ('abcde', 'ace', 3), ('abc', 'abc', 3), ('abc', 'def', 0), ('', 'abc', 0), ('bl', 'yby', 2), ] for a, b, exp in tests: ln, path = lcs_path(a, b) ok = 'OK' if ln == exp else 'FAIL' print(f'{a!r} vs {b!r} -> len={ln} path={path!r} {ok}')

('bl', 'yby')这组比较有意思，两个串没有相同字符，答案 0，回溯时应该一个字符都不输出。空串那组用来验证初值处理，如果 dp 表开成 n×m 而不是 (n+1)×(m+1)，这里会直接抛下标越界。

4.3 大输入规模下的适配：从 O(nm) 到 O(n log n)

前面说了，LCS 的 O(nm) 在 n、m 到 10^3 甚至 10^4 的时候都没问题，但题目一旦给到 10^5，就必须换思路。最典型的是在线评测平台上那道经典的 P1439 模板题：给两个 1 到 n 的排列，求最长公共子序列。

关键突破口在于：两个串都是排列，元素互不相同。那么我们可以把第一个排列中的每个值映射成它的位置下标，然后拿第二个排列去查这些下标，得到一个下标序列。求这两个排列的 LCS，等价于求这个下标序列的最长上升子序列。

为什么等价？因为公共子序列要求两个串里都出现，且在两个串中的相对顺序一致。第一个串里的顺序就是下标自然序，所以第二个串里的元素要按照在第一个串中出现的先后排列，也就是下标严格上升。于是问题转成了 LIS。

LIS 有 O(n log n) 的解法，用二分维护一个"最小尾部"数组：

import bisect def lcs_permutation(a, b): n = len(a) pos = [0] * (n + 1) for idx, v in enumerate(a): pos[v] = idx seq = [pos[v] for v in b] tails = [] for x in seq: i = bisect.bisect_left(tails, x) if i == len(tails): tails.append(x) else: tails[i] = x return len(tails)

这里的tails[k]表示"长度为 k+1 的上升子序列中，最小的末尾元素"。这个数组本身是严格递增的，所以可以二分。这道题的转换思路我印象特别深，因为它示范了一件事：很多看起来必须 O(nm) 的问题，换个等价描述就能降一个量级。

4.4 小数据对拍：省时间的验证方式

写完 O(n) 的 Kadane 或者滚动的 LCS 之后，我心里的第一反应不是"应该对了"，而是"找个可信版本对拍一下"。做法是写一个明显正确但很慢的版本（比如 O(n^3) 的暴力），随机生成几百组小数据，两个版本跑同样的输入，比对结果。

import random def check_max_subarray(rounds=500): for _ in range(rounds): n = random.randint(1, 8) arr = [random.randint(-10, 10) for _ in range(n)] fast = max_subarray(arr) slow = max(arr[i:j+1] and sum(arr[i:j+1]) for i in range(n) for j in range(i, n)) # 上面这行写法不严谨，实际用嵌套循环更清楚 if fast != slow: print('mismatch', arr, fast, slow) return print('all passed')

对拍这个习惯值多少钱？我自己算过，它能挡掉我至少一半的低级错误，尤其是边界和下标类的问题。写对拍只要五分钟，找 bug 可能要半小时，账很好算。

5. 常见问题与排查技巧实录

5.1 三类高频翻车现场

第一类是状态定义和答案位置不匹配。最大子段和的 dp 定义在"以 i 结尾"，答案就必须扫一遍所有 dp 取最大；最长公共子串同理。如果你直接返回 dp[n] 或者 dp[n][m]，在答案不以末尾结尾的题上必错。判断方法很简单：问自己一句"最优解一定在最后一个位置吗"，不是的话就必须全局取max。

第二类是边界语义没对齐。全负数数组返回 0 还是返回最大负数，取决于题目允许不允许空。这个错误特别隐蔽，因为大部分测试数据都是正负混合，恰好能过，只有专门的全负数测试点会挂。我现在的习惯是写完先在脑子里过一遍"全负数、全正数、含零、单元素、两个空串"这五组。

第三类是空间优化时把依赖关系搞乱。滚动数组里，dp[i-1][j-1] 这个"左上"的值是最容易被覆盖的，必须用临时变量提前存。LCS 滚动那版我第一次就栽在这上面。排查方法是把行和列的语义写在注释里，逐个对照row[j]旧值、row[j-1]新值、prev分别代表哪个格。

5.2 问题速查表

这张表里的每一条，我要么自己踩过，要么在别人的代码里见过，不是凭空列的。

5.3 我个人踩过的几个坑

第一个坑是"想当然的空间压缩"。有段时间我看 LCS 的二维表不顺眼，动手改成滚动数组，结果写完直接错了。后来复盘发现，我改的时候脑子里想的是"只需要上一行"，但忘了 dp[i][j-1] 是本行新算出来的值，这个依赖是"左边"。二维 DP 的滚动，永远是"上一行 + 当前行已经算出来的部分"，这一点想清楚了再动手，能少很多返工。

第二个坑是"用 0 当作不可达标记"。最大子矩阵和那道题里，如果初始 best 设成 0，遇到全负矩阵就会输出 0，而正确答案是最小的那个负数。那之后我一律用-10**18这种明确不可达的值做初值，虽然丑一点，但不骗自己。

第三个坑是"对拍数据分布太单一"。早期我造对拍数据都用random.randint(-10, 10)，结果全是正负混合，全负数的情况几乎撞不上。后来改成有意识地混入全负、全零、单元素这些边界，才真正起到防护作用。数据造得随机，不代表覆盖得全面。

6. 这两个模型还能往哪延展

6.1 最大子段和的线段树版本

如果题目要求支持单点修改，再查询区间最大子段和，Kadane 就不够用了，得请线段树出场。每个节点维护四个值：区间和sum、最大前缀和pre、最大后缀和suf、区间最大子段和best。

合并两个子节点时：

sum = l.sum + r.sum pre = max(l.pre, l.sum + r.pre) suf = max(r.suf, r.sum + l.suf) best = max(l.best, r.best, l.suf + r.pre)

这四个式子背后的逻辑都很直白。比如pre，要么完全落在左区间里，要么覆盖整个左区间再延伸到右区间，两种情况取大。best则要么在左边、要么在右边、要么跨中间（左后缀 + 右前缀）。

单点修改和区间查询都是 O(log n)，整体 O(n log n) 建树加 O(log n) 每次操作。我在做一道"带修改的区间最大子段和"题时，一开始想用分块糊过去，结果写了两百多行还过不了，换成线段树之后代码短了一半，效率还高。这个结构值得专门花时间掌握。

6.2 和背包问题在思维上的互通

有人觉得序列DP和背包DP是两套东西，其实底层思维方式是一致的：都是"在某个位置做决策，决策影响后续状态"。背包问题的 dp[i][j] 表示"前 i 个物品、容量 j 下的最大价值"，转移是选或不选；LCS 的 dp[i][j] 表示"前 i 个和前 j 个字符下的最长公共子序列"，转移是匹配或不匹配。

共同点在于：状态里包含了"处理到哪了"这个进度信息，转移就是在当前位置做一次选择。背包的一维滚动和 LCS 的滚动数组，本质也是同一件事——把只依赖上一层的维度压掉。学完这两个模型再去写 01 背包，很多人会发现原来那些"倒序枚举容量"的技巧，和 LCS 里保存"左上值"的技巧是同源的。

顺带提一句，动态规划在工程侧的应用也很广，比如资源调度、路径规划、库存分配这类问题，本质上都是"分阶段决策 + 状态转移"的模型，只是状态空间比刷题时大得多，工程上通常还要配合状态压缩和剪枝。

6.3 后续练习路线

如果这两道题你已经能独立写出来，包括边界、滚动优化、路径回溯，那接下来可以按这个顺序往下走：

先做最长上升子序列，把 O(n^2) 和 O(n log n) 两版都写一遍，顺便把二分的过程吃透。然后做编辑距离和最长公共子串，感受同一套二维骨架的变体。再往上就是区间DP，从石子合并、最长回文子序列这类题入手，体会区间状态怎么定义。最后是树形DP和状态压缩，把"状态"这个概念从数组下标扩展到集合和树节点上。

每一步都别跳过对拍和边界测试。我见过太多人一路刷题一路背模板，遇到变形题就懵。真正把状态定义、转移依据、空间时间优化这三件事想明白，后面无论遇到什么新题型，你都有办法自己推出来。

最后分享一个我用了很久的小技巧：每道DP题做完之后，用一句话把状态定义写下来，贴在代码注释第一行。比如"dp[i] 表示以 i 结尾的最大子段和"。这句话写不出来，说明状态没想清楚；写出来了但代码跟它对不上，说明转移写错了。这个习惯帮我在复盘时省了大量时间，也让我后来给别人讲题时能张口就说清楚每一个下标在干什么。