题目重点：维护各长度递增子序列的最小尾值，解释tails不是答案路径，并推导重复值与重建。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练子序列允许跳过位置，但原顺序不变；严格递增，相等值不可扩展长度。
- 只返回长度，空数组0；输入数值可比较，示例整数。
- 若输出实际子序列，要另存前驱和索引，不能直接返回tails。
解题路线
- O(n²)DP定义dp[i]为以位置i结束的最优长度，扫描此前所有更小值即可；二分优化将状态按长度聚合，而非逐结束位置保留。
- tails[l−1]表示已扫描前缀中，长度l递增子序列能达到的最小末值。同长度末值越小，未来越容易接新数，因此其余更大末值对求长度可丢弃。
- tails严格递增：长度l+1的任意递增序列去掉最后值，产生长度l且尾值更小，长度l最小尾值不超过它。于是可对tails做lower_bound。
- 处理x时找第一个tails[p]≥x。p之前所有尾值<x，可以把x接到长度p的序列后，产生长度p+1；在p处用x替换减少或保持尾值，p等于当前长度则追加。
- 为什么不改更长状态：在x之前不存在末值<x的长度p+1序列，否则lower_bound应更靠右；所以x不能形成更长序列。更短状态已有更小尾值，也无需替换。
- 重复值用第一个≥x，不能用第一个>x，否则[2,2]会错算长度2。若题目改为非递减子序列，则应换upper_bound，明确这个合同变化。
- tails的不同项可能来自不同历史子序列，如[3,5,6,2,4]最后tails=[2,4,6]，并非按原索引出现的合法完整序列。重建需存每个长度末项位置，并为新位置保存上一长度的末项前驱，最后沿前驱倒追。
手动走一遍
[10,9,2,5,3,7,101,18]最终长度4，可取2,3,7,18。[2,2,2]严格递增长度1。替换tails末值并非删除原数组元素，只是更新后续可扩展状态。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def lower_bound(values, target):
left, right = 0, len(values)
while left < right:
mid = (left + right) // 2
if values[mid] < target:
left = mid + 1
else:
right = mid
return left
def lis_length(values):
tails = []
for value in values:
position = lower_bound(tails, value)
if position == len(tails):
tails.append(value)
else:
tails[position] = value
return len(tails)
复杂度
O(n log n)时间，tails最多n项，O(n)工作空间；前驱重建也O(n)空间。数值比较成本按类型另计。
易错点与追问
容易失分的边界
- 用upper_bound把重复值算进严格递增。
- 将tails直接当真实答案序列。
- 把子序列误成连续子数组。
- 声称贪心只保留一个完整路径就能无条件扩展。
继续深挖
- 如何重建一条LIS？
- 怎样计算最长非递减子序列？
- 如何数最优子序列数量？
- 要在线删除或修改值时tails为什么不足？
