最长递增子序列 LIS
让最小结尾，一步步生长
先预测，再验证：先点重置。每次读入前，判断待读值会替换 tails 的哪一项，还是追加到末尾；点“下一步”对照，并说明为什么长度不变或增加 1。
原数组：真实子序列
nums = [3, 5, 7, 1, 2, 8]最长路径已读、未入路径本步输入未读
真实路径 [3, 5, 7, 8] · 下标 [0, 1, 2, 5]
最小结尾分布
tails = [1, 2, 7, 8]横轴：子序列长度。每根柱条独立记录最小结尾。
完整结果。点击重置，从第一个数重新推演。 窄屏图形可左右滑动；聚焦进度条后可用方向键调节。
换一组，验证你的理解
看完图，带走这些结论
最长递增子序列（LIS）是在保持原顺序、允许跳过元素的前提下，能取出的最长严格递增序列。维护每种长度的最小结尾 tails，其长度就是 LIS 长度。
适用条件与边界
原数组无需排序，也不能先排序再求原问题。严格递增不允许相等；非下降允许相等。空数组长度为 0，单元素长度为 1。图形输入限制为 1–12 个 ±999 整数。
始终保持的规律
tails[i] 是已读前缀中，长度 i + 1 的递增子序列的最小结尾。它的长度是答案，但这些结尾未必来自同一条子序列。
逐步例子
- 输入 [3, 5, 7, 1, 2, 8]：依次读 3、5、7，tails 从 [] 延长为 [3, 5, 7]。
- 读 1：替换第一个 ≥ 1 的结尾，得到 [1, 5, 7]；读 2 后得到 [1, 2, 7]。长度仍是 3。
- 把 tails 的位置看作候选：严格递增判断 tails[i] ≥ x，非下降判断 tails[i] > x。tails 有序，所以两种判定都从 false 变为 true；二分寻找第一个 true。若所有位置都是 false（也包括空 tails），lower_bound / upper_bound 返回尾后位置 end，此时追加 x，不能解引用 end。
- 读 8：没有 ≥ 8 的结尾，追加为 [1, 2, 7, 8]。答案长度 4；一条真实子序列是 [3, 5, 7, 8]。
复杂度
用随机访问数组保存 tails，并用二分定位时，最坏时间 O(n log n)，额外空间 O(n)；空数组 O(1)。页面复制逐帧快照的开销不代表算法本身的空间复杂度。
常见误区
- 把 tails 当作答案序列：各格可能来自不同子序列，恢复具体答案需要额外记录前驱。
- 严格递增找第一个 ≥ x 的位置（lower_bound）；非下降找第一个 > x 的位置（upper_bound）。[2, 2, 2] 的两种答案分别是 1 和 3。
- 子序列不要求连续。替换一个结尾不表示改动原数组，也不增加当前答案长度。
- 长度相同，方案数也相同吗？[1, 3, 2] 与 [3, 1, 2] 最终 tails 都是 [1, 2]、LIS 长度都是 2。前者有 [1, 3]、[1, 2] 两条，后者只有 [1, 2] 一条。每种长度仅留一个最小结尾的普通 tails，最终状态不足以确定方案数。计数还需额外状态，例如记录以每个原下标结尾的最优长度及方案数：更长时替换计数，同长时累加。
- 重复值怎样计数？这里按原数组下标选择区分方案。[2, 2, 2] 严格递增的最长长度为 1，有 3 种下标选择；按值序列去重则只剩 [2] 一种，是另一种计数口径。允许相等时，最长非下降长度为 3，只有选取全部三个下标这 1 种。上图展示长度和一条路径；同步代码只求长度，两者都不计算方案总数。
自测与答案
输入 [3, 5, 7, 1, 2, 8]，最终 tails = [1, 2, 7, 8]。它是一条原数组子序列吗？
不是。7 在 1、2 之前，不能按这个顺序取出。长度 4 仍然正确，例如原数组里的 [3, 5, 7, 8]。tails 保存的是各个长度的最小结尾。
应用：最少删除与移动
- 最少删除几个元素？ 设原数组长度为 n，LIS 长度为 L。严格递增的剩余元素仍是原数组子序列，最多保留 L 个；保留一条真实 LIS、删除其余元素即可，所以最少删除 n−L 个。目标若是允许相等的非下降序列，则用 n−LNDS，LNDS 表示最长非下降子序列的长度。例如 [3, 5, 7, 1, 2, 8] 保留 [3, 5, 7, 8]，删除 1、2，只需 6−4=2 次。
- 取出再插回，排序要移动几次？ 先限定元素互不相同，一次移动是取出一个元素、再插回任意位置。做 m 次移动后，至少 n−m 个从未被取出的元素保持原有相对顺序；排序后它们必须递增，所以 m≥n−L。反过来，保留一条真实 LIS 作锚点，将其余元素按值从小到大，分别插到下一个更大锚点之前（没有则放到末尾），每个至多移一次。因此最少也是 n−L 次。保留的是相对顺序，数组下标可以改变；不能把 tails 直接当作锚点。
- 重复值和交换也能照搬吗？ 有重复值且目标是非下降排序时，取出再插回的最少次数为 n−LNDS；保留一条真实 LNDS，再按目标顺序放入其余元素。重复值无法只靠重排变成严格递增。交换两个元素是另一种操作：[3, 2, 1] 需要两次取出再插回，却只需交换首尾一次。这里讨论整个剩余序列有序，不是“最多删除 K 个后寻找最长连续递增片段”。上图展示长度和一条真实路径；同步代码只求长度，两者都不生成删除或移动指令。
延伸学习
同样是找第一个 true，候选可以从 tails 的位置换成时间。注意：本课可能返回 end，表示没有满足条件的元素；二分答案课先证明 hi 可行，才在闭区间里收缩。不能把两者的区间边界与无解处理直接混用。