Salesforce LIS：严格递增子序列的 DP 与二分 tails

题意与假设

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

• 子序列保持原下标顺序但可跳过元素；严格递增意味着相等值不能接在一起。返回长度，空数组返回 0。
• 整数可负、可重复；代码只计算长度，不重建实际 LIS。如需返回序列要额外记录前驱。
• 数组可在内存中遍历一次；不依赖数值范围，也不先排序原数组，排序会破坏子序列的顺序信息。

解题路线

1. 暴力枚举所有 2^n 个子序列并检查是否严格递增，清楚但指数级。进而用 dp[i] 表示以 nums[i] 结束的 LIS 长度：1+max(dp[j])，其中 j<i 且 nums[j]<nums[i]，没有前驱则为 1；时间 O(n²)。
2. 优化为 tails[len−1]：所有长度为 len 的递增子序列中最小的末尾值。处理 value 时，用 bisect_left 找第一个 >=value 的位置并替换；若位置在 tails 末尾则追加。较小尾值给后续元素留下更大延伸空间。
3. tails 始终递增，长度等于当前前缀的 LIS 长度，但 tails 本身未必是一条真实子序列；替换只是更新该长度最有利的末尾。对相等值用 lower_bound/bisect_left，确保不增加严格递增长度。

手动走一遍

nums=[10,9,2,5,3,7,101,18]：tails 依次从 [10]、[9]、[2]、[2,5]、[2,3]、[2,3,7] 到长度 4；处理 18 时替换 101，最终 tails=[2,3,7,18]，答案 4。nums=[2,2,2] 每次都替换首位，答案 1。

Python 参考实现

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

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

from bisect import bisect_left


def lis_length(nums: list[int]) -> int:
    """Length of a strictly increasing subsequence."""
    tails: list[int] = []
    for value in nums:
        position = bisect_left(tails, value)
        if position == len(tails):
            tails.append(value)
        else:
            tails[position] = value
    return len(tails)

复杂度

n 个元素各在最长 n 的 tails 上二分一次，时间 O(n log n)、辅助空间 O(n)。O(n²) DP 易于输出前驱与路径；若 n 很小或要解释完整状态，它也是合理主解。

易错点与追问

容易失分的边界

• 用 bisect_right 处理严格递增，会把相等元素接成更长序列；非严格递增才考虑右边界。
• 把 tails 当成实际 LIS 直接返回；不同长度的最小尾元素可能来自不兼容的历史路径。
• 先排序 nums 再求递增长度，破坏原序，得到的结果没有子序列意义。
• 用连续子数组窗口求解，把 subsequence 错读为 substring。

继续深挖

• 若需输出实际 LIS，给每个元素存前驱索引、每种长度当前最优尾索引，最后回溯。
• 若改为最长非递减子序列，相等值可以延伸，二分位置应使用 bisect_right。
• 若要统计最长递增子序列的个数，普通 tails 长度信息不足；需另用 DP 或带计数的数据结构。