必须用 std::lower_bound，因为它在严格递增的 tails 数组中查找第一个 ≥ num 的位置以正确替换，维持“长度为 i+1 的递增子序列最小结尾值”性质；用 upper_bound 或手写错误边界会导致结果偏短。
为什么 std::lower_bound 要在单调数组里找插入位置
因为最长递增子序列（LIS）的二分优化本质不是在原数组上操作，而是在维护一个「可能的最小结尾数组」——它严格递增，且 tails[i] 表示长度为 i+1 的递增子序列中，最小可能的结尾值。
这个数组天然有序，所以每次新元素进来，用 std::lower_bound 找第一个 ≥ 它的位置，直接替换，就能维持性质。错用 std::upper_bound 或手写错边界，会导致覆盖错误位置，结果偏短。
- 必须用
std::lower_bound(tails.begin(), tails.end(), num)，不是upper_bound -
tails初始为空，每轮 push_back 或 replace，不排序、不 reverse - 原数组有重复值时，
lower_bound保证相同值被“覆盖”而非跳过，这对非严格递增（即允许相等）场景要改逻辑
C++ 里怎么写对 tails 数组的二分更新
关键不是写二分模板，而是让容器支持随机访问 + 长度可变。std::vector 是唯一合理选择；用 std::set 或 std::deque 都会破坏 O(1) 访问或引入额外 logN 开销。
常见错误是每次 push_back 后再调 sort，这退化成 O(N²logN)；或者误用 insert 导致大量内存搬移。
立即学习“C++免费学习笔记（深入）”；
- 初始化：
vector<int> tails;</int> - 对每个
num：用auto it = lower_bound(tails.begin(), tails.end(), num); - 若
it == tails.end()，tails.push_back(num)；否则*it = num - 最终 LIS 长度就是
tails.size()，不是tails.back()
DP 基础版为啥容易写成 O(N²) 还超时
二维 DP 状态定义简单：dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。但转移时必须从 j = 0 到 i-1 全扫一遍，检查 nums[j] ，这就是纯暴力嵌套循环。
很多人卡在边界初始化（dp[i] 至少为 1）和 max 更新时机，更隐蔽的问题是：没提前 break、用了 vector<vector>></vector> 存路径导致内存爆炸、或把 max_len 放在内层循环末尾却忘了在外层取全局最大。
-
dp[i] = 1初始化必须做，不能依赖默认值 - 内层循环后要执行
max_len = max(max_len, dp[i])，不是只在最后算一次 - 若题目只要长度，别开
prev[]数组存路径；要路径才额外处理 - O(N²) 在 N > 1e4 时大概率超时，此时必须切到二分优化版
二分优化版能还原实际子序列吗
不能直接还原。因为 tails 数组里的值不对应原序列中的连续/真实索引位置，只是“长度为 k 的子序列结尾最小能是多少”的抽象记录。
想输出任意一个 LIS（不止长度），得回到 DP 基础版，加一个 prev[i] 记录前驱下标，最后倒推。二分法只负责高效求长度，混用两种思路极易出错。
- 如果只要长度：用二分优化，快且省空间
- 如果要输出子序列：老老实实用 DP +
prev数组，O(N²) 时间 + O(N) 空间 - 想兼顾？可以二分法过程中同步维护
parent和index映射，但代码复杂度陡增，边界极难验证
真正难的不是写对算法，是看清题目到底要什么——长度还是序列本身。漏读这一行，后面全白调。
