std::lower_bound可实现O(n log n)严格递增LIS长度计算，维护最小末尾数组并二分替换首个≥当前数位置，避免upper_bound导致重复元素误入；输入{10,9,2,5,3,7,101,18}得长度4。
用 std::lower_bound 实现 O(n log n) 的 LIS 长度计算
直接求最长递增子序列（LIS）长度，不用还原具体序列时，std::lower_bound 是最实用的选择。它维护一个「可能的最小末尾数组」，每次用二分替换掉第一个 ≥ 当前数的位置，保证数组始终单调递增且尽可能“紧凑”。
常见错误是误用 std::upper_bound —— 它会导致重复元素被错误接纳，破坏严格递增语义；严格递增必须用 lower_bound。
- 输入数组为
nums = {10, 9, 2, 5, 3, 7, 101, 18}，最终维护的辅助数组可能是{2, 3, 7, 18}（长度 4），但该数组不一定是真实子序列，仅长度准确 - 时间复杂度稳定 O(n log n)，空间 O(n)；比暴力 DP 的 O(n²) 快得多，尤其适合 n > 1e4 的场景
- 注意：该方法只适用于「严格递增」（
a[i] ）。若需「非递减」（允许相等），应改用 <code>upper_bound
vector<int> tails;
for (int x : nums) {
auto it = lower_bound(tails.begin(), tails.end(), x);
if (it == tails.end()) tails.push_back(x);
else *it = x;
}
return tails.size();
还原具体的 LIS 路径需要额外记录 parent 和 index
只算长度容易，但面试或调试时常需返回任意一个最长递增子序列（比如 {2, 3, 7, 18}）。这时不能只靠 tails 数组，必须在构建过程中同步记录每个位置的前驱索引。
关键点在于：每次更新 tails 中某个位置时，要记下「谁导致了这次更新」——即当前元素在原数组中的下标，以及它接在哪个已有元素之后。
立即学习“C++免费学习笔记（深入）”；
- 声明两个辅助数组：
prev[i]表示nums[i]在 LIS 中的前一个元素下标，初始为 -1；tail_indices[k]记录长度为 k+1 的 LIS 的末尾元素在nums中的下标 - 每次调用
lower_bound得到插入位置pos后，若pos > 0，则prev[i] = tail_indices[pos-1] - 最后从
tail_indices.back()开始，沿prev链表反向构造结果（记得 reverse）
DP 做法（O(n²)）适合小数据或需要所有 LIS 变种时用
当 n ≤ 5000 或你需要统计 LIS 个数、求字典序最小的 LIS、或处理带权版本时，传统 DP 更灵活。核心状态是 dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。
容易踩的坑是内层循环边界写成 j 却忘了判断 <code>nums[j] ，导致非递增也被计入；还有人把初始化全设为 0，实际应全为 1（单个元素本身构成长度为 1 的序列）。
- 状态转移：
dp[i] = max(dp[i], dp[j] + 1)，仅当nums[j] - 若还需路径，同步维护
parent[i] = j即可 - 注意：该 DP 不保证全局最长序列一定以最后一个元素结尾，所以答案是
*max_element(dp.begin(), dp.end())
LeetCode 300 题默认要求的是长度，别自己加戏去还原序列
很多初学者看到「最长递增子序列」就默认要输出数组，但 LeetCode 第 300 题明确只要求返回长度。用 lower_bound 方法 5 行搞定，硬上 DP 或试图还原路径反而增加出错概率和运行时间。
真正需要路径的场景其实有限：调试验证、可视化、或题目明确说「返回任意一个」。否则优先选简洁、高效、不易错的长度解法。
最易被忽略的一点是：输入为空时，tails 初始化为空 vector，循环不执行，直接返回 0 —— 这个边界天然正确，不必特判，但有人会多此一举加 if (nums.empty()) return 0;，纯属冗余。
