最长递增子序列

每个数选或不选，会产生指数级组合。台阶是 2^n→O(n²)→O(nlogn)：先有以 i 结尾的朴素 DP（O(n²)，见后面面试追问 2），本课直接讲把“找位置”改成二分、降到 O(nlogn) 的 tails 写法。

tails[i] 表示长度 i 加 1 的递增子序列，能拥有的最小结尾。新数用二分找替换位置。

读 10：tails 是空的，10 直接追加。长度 1 的最小结尾是 10。

读 9 替换 10：9 不能让长度变长，但长度 1 的结尾从 10 降到 9，更有潜力。

读 2 再替换：2 更小，继续替换长度 1 的最小结尾。

读 5 追加：5 大于 tails 最后一个 2，可以接在后面，长度变成 2。

读 3 · 二分定位：关键的“定位”这一帧：3 不直接和末尾比，而是在 tails=[2,5] 里二分。l=0、r=2，mid=1 看到 tails[1]=5≥3，所以要替换的就是下标 1 这一格（高亮处）。

读 3 替换 5：二分定位到下标 1，把该格从 5 换成 3：长度没变（仍 2），但长度 2 的结尾被压低，潜力更好。

读 7 追加：二分发现 7 比所有结尾都大（落到末尾），追加后长度变 3。tails 的长度就是当前 LIS 长度。

读 101 追加：101 比末尾 7 还大，追加到末尾，长度变成 4——这就是答案 4 的来源，对应 [2,3,7,101]。

读 18 替换 101：最后一个数 18：二分定到下标 3，把 101 压低成 18，长度不变仍是 4。整段跑完 result=4，与题面示例完全对上。

tails 的替换不是删答案，而是在保留更好的潜力。

边界三连：相等、递增、递减，能测出 lower_bound 是否选对。

雷区实演 · 相等不能追加：[2,2,2] 每个 2 都替换第一个不小于 2 的位置，tails 长度一直是 1。

面试追问 1：tails 只给长度，要还原序列得额外记录每个数的下标和前驱。

面试追问 2：朴素 DP：dp[i] 是以 i 结尾的最长长度，往前枚举所有更小的前驱。

面试追问 3：严格用 lower_bound，非严格用 upper_bound，差别只在“相等”怎么处理。

这题学完不要乱跳，下一步去 对应专题 连刷同类题；卡住时用 AI 答疑追问“为什么这一步成立”，比只背答案更稳。