# 最长递增子序列（LIS）图解：替换结尾，还是延长

一步一格观察 tails，切换严格递增与非下降，理解相等元素为何不能延长严格 LIS。

原文 / Canonical: https://crazycloud.cc/learn/longest-increasing-subsequence
作者: crazycloudcc
首次发布: 2026-10-07
更新: 2026-10-15

本阅读版与网页共用课程数据；互动请访问原文。

## 一句话答案

最长递增子序列（LIS）是在保持原顺序、允许跳过元素的前提下，能取出的最长严格递增序列。维护每种长度的最小结尾 tails，其长度就是 LIS 长度。

## 适用条件与边界

原数组无需排序，也不能先排序再求原问题。严格递增不允许相等；非下降允许相等。空数组长度为 0，单元素长度为 1。图形输入限制为 1–12 个 ±999 整数。

## 不变量

tails[i] 是已读前缀中，长度 i + 1 的递增子序列的最小结尾。它的长度是答案，但这些结尾未必来自同一条子序列。

## 逐步例子

1. 输入 [3, 5, 7, 1, 2, 8]：依次读 3、5、7，tails 从 [] 延长为 [3, 5, 7]。
2. 读 1：替换第一个 ≥ 1 的结尾，得到 [1, 5, 7]；读 2 后得到 [1, 2, 7]。长度仍是 3。
3. 把 tails 的位置看作候选：严格递增判断 tails[i] ≥ x，非下降判断 tails[i] > x。tails 有序，所以两种判定都从 false 变为 true；二分寻找第一个 true。若所有位置都是 false（也包括空 tails），lower_bound / upper_bound 返回尾后位置 end，此时追加 x，不能解引用 end。
4. 读 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 保存的是各个长度的最小结尾。

## 应用：最少删除与移动

1. **最少删除几个元素？** 设原数组长度为 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 次。
2. **取出再插回，排序要移动几次？** 先限定元素互不相同，一次移动是取出一个元素、再插回任意位置。做 m 次移动后，至少 n−m 个从未被取出的元素保持原有相对顺序；排序后它们必须递增，所以 m≥n−L。反过来，保留一条真实 LIS 作锚点，将其余元素按值从小到大，分别插到下一个更大锚点之前（没有则放到末尾），每个至多移一次。因此最少也是 n−L 次。保留的是相对顺序，数组下标可以改变；不能把 tails 直接当作锚点。
3. **重复值和交换也能照搬吗？** 有重复值且目标是非下降排序时，取出再插回的最少次数为 n−LNDS；保留一条真实 LNDS，再按目标顺序放入其余元素。重复值无法只靠重排变成严格递增。交换两个元素是另一种操作：[3, 2, 1] 需要两次取出再插回，却只需交换首尾一次。这里讨论整个剩余序列有序，不是“最多删除 K 个后寻找最长连续递增片段”。上图展示长度和一条真实路径；同步代码只求长度，两者都不生成删除或移动指令。

## 延伸学习

同样是找第一个 true，候选可以从 tails 的位置换成时间。注意：本课可能返回 end，表示没有满足条件的元素；二分答案课先证明 hi 可行，才在闭区间里收缩。不能把两者的区间边界与无解处理直接混用。

[继续探索：二分答案，寻找第一个可行时刻](https://crazycloud.cc/learn/binary-search-on-answer)

## 参考资料

- [CP-Algorithms：Longest increasing subsequence](https://cp-algorithms.com/dynamic_programming/longest_increasing_subsequence.html)
- [C++ 工作草案：lower_bound / upper_bound](https://eel.is/c++draft/alg.binary.search)

[推导与 C++ 代码](https://crazycloud.cc/blog/longest-increasing-subsequence)