核心概述
最长上升子序列（LIS）：在序列中寻找严格递增的最长子序列，可在 O(n log n) 下求长度并按需重构方案，且可切换为非降等常见变体。
原文引述
Description: Compute LIS in O(n log n) via patience sorting (tails) with binary search; supports reconstruction and non-decreasing variant by switching lower/upper_bound.（摘自本节点现有英文注释） Time: O(n log n)（摘自本节点现有英文注释） Status: tested（摘自本节点现有英文注释）
展开阐述
-
定义与变体
- 严格上升：a[i1] < a[i2] < … < a[ik]（经典 LIS）
- 非降序列：a[i1] ≤ a[i2] ≤ …（将 lower_bound 改为 upper_bound）
- 重构方案：用前驱数组记录每个位置的连接来源，以回溯一条合法的 LIS
- 值域处理：当值域很大或需要等值细化策略时可进行离线坐标压缩
-
算法一：O(n^2) DP
- 状态：dp[i] 表示以 i 结尾的 LIS 长度
- 转移：dp[i] = 1 + max{ dp[j] | j < i 且 a[j] < a[i] }
- 答案：max_i dp[i]
- 复杂度：O(n^2)，实现简单，适合中小规模
-
算法二：O(n log n) 二分（“扑克牌接龙”/patience sorting）
- 维护 tails，其中 tails[len-1] 记录“长度为 len 的上升子序列的最小可能结尾值”
- 对每个 a[i]：
- it = lower_bound(tails.begin(), tails.end(), a[i])（严格上升）
- it == tails.end() 则追加，否则覆盖 *it
- 若需非降，将 lower_bound 改为 upper_bound
- 可同时维护 pos[len-1] 为尾元素下标，以及 prev[i] 前驱下标以支持重构
-
代码框架（重构严格 LIS）
// 返回 LIS 长度，并在 seq 中放入一组 LIS（按原序重构）
int lis(const vector<int>& a, vector<int>& seq) {
int n = (int)a.size();
vector<int> tails; // 仅存值，用于长度
vector<int> pos; // 每个长度对应的尾元素下标
vector<int> prev(n, -1); // 前驱下标，用于重构
tails.reserve(n);
pos.reserve(n);
for (int i = 0; i < n; ++i) {
auto it = lower_bound(tails.begin(), tails.end(), a[i]); // 严格上升
int j = int(it - tails.begin()); // j 为新长度-1
if (it == tails.end()) {
tails.push_back(a[i]);
pos.push_back(i);
} else {
*it = a[i];
pos[j] = i;
}
if (j > 0) prev[i] = pos[j-1];
}
// 重构
seq.clear();
for (int p = pos.back(); p != -1; p = prev[p]) seq.push_back(a[p]);
reverse(seq.begin(), seq.end());
return (int)tails.size();
}-
复杂度与边界
- O(n log n) 求长度，空间 O(n)；重构为线性时间追加
- 严格/非降的等值处理需与 lower/upper_bound 的选择一致
- 二维点集等变体常用“一维排序，另一维做 LIS”，相等时排序方向需与“严格/非降”保持一致
-
正确性要点
- 不变式：tails 维护“同长度最优结尾值”，更小的结尾更利于后续扩展
- 结构保真：通过 pos/prev 保留路径信息，不影响长度计算的正确性