本讲定位：上一讲我们建立了”递归 → 记忆化 → 递推”的思维路径，例题的状态都”长在题面上”（行号、列号）。本讲开始自己设计状态，主角是一维序列上的三大经典模型：最大子段和、最长上升子序列（LIS）、最长公共子序列（LCS）。它们是后续一切 DP 的词汇表。
前置知识：专题一（递归到递推）；
lower_bound的用法（进阶部分用到）。标注 ⭐ 的小节为进阶内容（提高组），第一遍学习可跳过。
线性 DP：状态沿着序列的下标”一维地”推进，$f[i]$ 只依赖前面的 $f[j]\ (j < i)$。它是形态最简单的 DP，但覆盖了状态设计中最重要的一个套路：
“以 $i$ 结尾”三个字，是线性 DP 的万能钥匙。
为什么？直接定义”前 $i$ 个数的答案”往往无法转移——因为不知道前面的方案”接不接得上”第 $i$ 个数。而”以 $i$ 结尾”把接口固定住了：想接上 $a_i$，只需检查结尾元素。状态定义中多说死一点，转移就少猜一点——这是设计状态的第一课。
题意：给长度为 $n$（$n \le 2 \times 10^5$）的整数序列，求一段连续非空子段，使其和最大。
样例：
2 -4 3 -1 2 -4 3→ 答案4（子段 $3, -1, 2$）。
错误的起手式：设 $f[i]$ 为”前 $i$ 个数中的最大子段和”。转移时想接上 $a_i$，却不知道最优子段是否恰好停在 $i-1$——状态描述太松，接不上。
正确的状态：
$$ f[i] = \text{以 } a_i \text{ 结尾的最大子段和} $$
以 $a_i$ 结尾的子段只有两种形态：要么是 $a_i$ 自己单独一段，要么是”以 $a_{i-1}$ 结尾的某个子段”再接上 $a_i$。要最大，前者取 $a_i$，后者取 $f[i-1] + a_i$：
$$ f[i] = \max(f[i-1] + a_i,\ a_i) $$
最终答案是 $\max_i f[i]$（最优子段总得以某个位置结尾）。由于 $f[i]$ 只依赖 $f[i-1]$，连数组都可以省掉：
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
scanf("%d", &n);
int f = 0, ans = INT_MIN;
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
f = (i == 1) ? x : max(f + x, x); // f：以第 i 个数结尾的最大子段和
ans = max(ans, f);
}
printf("%d\n", ans);
return 0;
}
复杂度 $O(n)$。经典陷阱：子段非空，全负数时答案是最大的那个负数，不是 $0$——所以 ans 初值必须是 INT_MIN，且不能把 f 与 $0$ 取 $\max$。