Meta 严格递增子序列：tails二分与见证路径

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 子序列保持原顺序但可跳元素，严格递增，等值不能增加长度；空数组结果0。
• 代码返回长度，不假装tails本身就是原数组中的合法最优子序列。

解题路线

1. 定义tails[k]为已处理前缀中长度k+1的递增子序列能达到的最小尾值。新value二分第一个>=value位置，替换该位置以降低尾部，或位于末尾则扩长。
2. 最小尾更有利于后续接值，替换不会减少任何已有可达长度。严格递增用lower_bound；若非降序允许相等，应改upper_bound。
3. tails各位置可能来自不同序列，所以只用它输出长度。要恢复实际路径，保存每元素prevIndex以及各长度尾元素index，最终从最长尾回溯。

手动走一遍

[10,9,2,5,3,7,101,18]长度4，例如[2,3,7,18]。遇3替换长度2的5，保留更小尾让7仍可接；[2,2,2]严格版长度1。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from bisect import bisect_left


def lis_length(values):
    """Strictly increasing subsequence, not contiguous; returns length."""
    tails=[]
    for value in values:
        index=bisect_left(tails,value)
        if index==len(tails):tails.append(value)
        else:tails[index]=value
    return len(tails)

复杂度

O(n log n)时间，O(n)最坏tails空间。恢复路径额外O(n)索引空间，不改变时间界。

易错点与追问

容易失分的边界

• 最长连续上升段与LIS不同，不能只在每次下降时重置长度。
• tails经过替换未必按原下标递增，直接返回它可能构造不存在的子序列。

继续深挖

• 求LIS数量时相同tails不足以保存不同路径数，需按值域维护(最大长度,计数)并正确合并相等情况。
• 要求在线删除旧元素的滑窗LIS不能直接删tails一个位置，结构依赖全前缀历史。