线性 DP：最长上升子序列

先试个「自然」的状态：

f[i] = 前 i 个数里最长上升子序列的长度

写转移的时候你会立刻卡住：a[i] 能不能接到那条子序列后面？ 不知道 —— 因为你不知道那条子序列的结尾是多少。

状态里缺了「接下来还能不能接」所需要的信息。补救办法就是把它塞进状态里：

f[i] = 以 a[i] 结尾的最长上升子序列长度

加了「以 a[i] 结尾」这五个字，结尾是谁就确定了（就是 a[i]），转移立刻能写：

f[i] = 1 + max{ f[j] : j < i 且 a[j] < a[i] }

万能问法还是那句（第 21 章）：倒数第二个数是谁？ 枚举它就行。

★ 这个补救办法叫无后效性：状态必须包含「后面做决定时要用到的全部信息」。 「以 i 结尾」是子序列 / 子段类问题的第一反应，遇到就先试它。

换一个角度记录信息：

tails[k] = 所有长度为 k+1 的上升子序列里，结尾最小的那个结尾值

为什么是「结尾最小」：结尾越小，后面越容易接上新的数。 同样长度的子序列我们只关心最好接的那一条，别的都可以扔掉。

★ 而它有个天生的性质：tails 一定是严格递增的。

反证：若 tails[k] >= tails[k+1]，那条长度 k+2、结尾是 tails[k+1] 的子序列， 去掉最后一个数，就得到一条长度 k+1、结尾比 tails[k+1] 还小的子序列 —— 比 tails[k] 更小，和「tails[k] 是最小结尾」矛盾。∎

递增 ⇒ 可以二分（第 8 章的 lower_bound 终于派上用场了）。于是扫每个 a[i]：

• 在 tails 里找第一个 >= a[i] 的位置 p；
• 找不到（a[i] 比所有都大）→ 接到末尾，最长长度 +1；
• 找到了 → 用 a[i] 顶掉 tails[p]（长度不变，但结尾更小，以后更好接）。

答案就是 tails 的长度。每个元素一次二分，总共 O(n log n)。

把动画播到最后，或者跑一下下面这份 trace：

点「运行 ▶」看结果

2 5 3 7 1 跑完，tails = [1, 3, 7]。

可是 1 在原序列里排在 7 的后面 —— [1, 3, 7] 根本不是这个序列的子序列！

但它的长度 3 是对的。真正的最长上升子序列是 2 5 7 或者 2 3 7。

tails 是「每种长度的最好结尾」的记录板，不是答案序列本身。 它中途会被改得面目全非，只有「长度」这一个数字是有意义的。

1. 转移时顺手记 pre[i] = 从哪个 j 转移过来的；
2. 从最优的那个下标出发，顺着 pre 一路往回走；
3. 走出来是倒着的，reverse 一下。

背包（第 23 章）、区间 DP（第 26 章）要输出方案时，用的是同一套动作。

顺带一提：check:viz 对这份代码做的是硬验证 —— 它会检查输出的序列真的严格递增、真的是原序列的子序列、长度真的等于答案。 只对长度不对方案的错误，普通对拍是抓不出来的。

两种写法在没有重复元素的序列上给出的答案完全一样。

所以随机造几组大数据测一测 —— 全过。交上去 —— WA。

本章的生成器把值域压到 1~4（重复满地都是）， 300 组数据里有 158 组两种写法答案不同。值域小才是这个生成器的灵魂，不是 n 大。

这也是第 20 章那条规矩的又一次应用： 随机的必须是「算法依赖的那个东西」 —— 这里依赖的是「有没有相等的数」。

【1】「以 i 结尾」是子序列类问题的默认状态。 状态里必须留下「后面还能不能接」所需要的信息 —— 这就是无后效性。 卡住的时候先问：我的状态漏了什么信息？

【2】「保留最优的那个代表」是一种通用的压缩手段。 tails 的本质是：同样长度的子序列有很多条，我只留结尾最小的那条当代表。 这个思路在很多优化里会再见到（第 35 章的单调队列就是同一个味道）。

【3】能二分的前提永远是单调，而这里的单调是「白送的」。 第 9 章的二分答案要你自己去证可行性单调；这一章的 tails 天生递增， 证明只有三行。看到一个天然有序的数组，就该想到二分。