o(n²)朴素dp在大数据上卡顿，因每个i需遍历所有j
为什么朴素DP的O(n²)会卡在大数据上
因为对每个位置 i，都要扫前面所有 j 找满足 <code>nums[j] 的最大 <code>dp[j]，当 n 到 1e5 时，操作量接近 10¹⁰，C++ 都扛不住。
核心思路：维护一个“可能的最小末尾”数组
不存所有可能的子序列，只存长度为 k 的递增子序列中，末尾元素最小的那个值 —— 记为 tail[k]。这个数组天然单调递增（可证），所以能二分。
遍历 nums[i] 时：
- 如果
nums[i] > tail.back()，直接追加：tail.push_back(nums[i]) - 否则，在
tail中找第一个 ≥nums[i]的位置（lower_bound），用nums[i]替换它
注意：替换不是破坏解，而是让后续更小的数有机会接上，保持“长度不变但末尾更小”的贪心性质。
vector<int> tail;
for (int x : nums) {
auto it = lower_bound(tail.begin(), tail.end(), x);
if (it == tail.end()) tail.push_back(x);
else *it = x;
}
return tail.size();</int>
为什么用 lower_bound 而不是 upper_bound
tail 存的是严格递增序列，我们要找第一个「不允许接在它后面」的位置（即 tail[k] >= x），这样才能保证替换后仍维持严格递增。用 upper_bound 会漏掉相等的情况，导致错误地延长长度。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
比如 nums = [1,1,1,1]，tail 最终应为 [1]（LIS 长度是 1），若误用 upper_bound，可能把新 1 插到末尾，变成 [1,1]，错。
不能直接还原具体子序列？那怎么输出路径
当前方法只求长度，tail 数组本身不是真实子序列（中间被多次覆盖）。要还原路径，得额外维护：
-
parent[i]：记录nums[i]在 LIS 中的前驱下标 -
pos[x]：记录长度为x的子序列末尾在原数组中的下标
每次在 tail 中二分定位时，同步更新 parent[i] = pos[len-1]（len 是插入后的新长度减 1）。空间和逻辑开销明显上升，实际中如无必要，别硬套。
真正容易被忽略的是：这个算法求出的长度绝对正确，但 tail 数组只反映“构造过程”，不是答案本身；想调试时打印 tail 看中间状态没问题，但千万别把它当结果子序列去交题。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
