求最长递增子序列。

核心回答

最长递增子序列要求保留原数组中的相对顺序，可以跳过元素，但相邻选中元素必须严格增大。通常先求长度；例如 [3, 5, 6, 2, 4, 7] 的答案是 4，可以选 [3, 5, 6, 7]。

有两种常用解法：

• 动态规划，O(n²)： dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。枚举前面的 j，若 nums[j] < nums[i]，就用 dp[j] + 1 更新。答案取整个 dp 的最大值。
• 最小结尾加二分，O(n log n)： tails[k] 保存已处理前缀中，长度为 k + 1 的递增子序列所能取得的最小结尾。依次处理每个值，用它替换第一个大于等于它的结尾；没有这样的结尾就追加。最后 tails 的长度就是答案。

两种方法都使用 O(n) 额外空间。tails 是不同长度的最优结尾记录，不一定是一条真实子序列。

先用动态规划把状态讲清楚

以 nums[i] 结尾的子序列，前一个元素只能来自 j < i 且 nums[j] < nums[i] 的位置。因此初始化每项为 1，再对这些位置取最大值：

dp[i] = max(1, 所有满足条件的 dp[j] + 1)。

从左向右计算，才能使用已经求出的前置状态。最终取 max(dp)，不能只返回最后一项。例如 [1, 2, 3, 0] 中，最后一个位置的长度是 1，整体答案却是 3。

def lis_length_dp(nums: list[int]) -> int:
    if not nums:
        return 0

    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

代码对空数组返回 0；非空数组至少可以选一个元素。它不修改输入，双层循环的时间复杂度是 O(n²)。

怎样优化到 O(n log n)

同样长度的递增子序列，结尾越小，后续能接上的数越多。因此不必保存所有候选，只需记录每个长度对应的最小结尾。

tails 本身严格递增，可以二分查找第一个 >= x 的位置 pos：

• 若 pos > 0，前一个结尾小于 x，所以存在长度为 pos 的子序列能接上 x。
• 若找到了位置，就把该长度的结尾替换成 x。得到更小或相同的结尾，不会降低以后接续的机会。
• 若 pos == len(tails)，说明 x 大于所有已记录结尾，可以把当前最长长度增加 1。

Python 的 bisect_left 正好返回这个位置。这里是替换或末尾追加，不能用有序插入把数组长度每次都增加。

from bisect import bisect_left


def lis_length(nums: list[int]) -> int:
    tails = []
    for x in nums:
        pos = bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)

以 [3, 5, 6, 2, 4, 7] 为例，tails 依次变成：

[3]、[3, 5]、[3, 5, 6]、[2, 5, 6]、[2, 4, 6]、[2, 4, 6, 7]。

长度是 4，但最后的 [2, 4, 6, 7] 不是原数组的子序列，因为 6 出现在 2 和 4 前面。算法保存的是各长度各自的候选结尾，不保证这些候选来自同一条链。

常见追问

为什么是第一个大于等于，而不是第一个严格大于？

本题要求严格递增，相同数字不能延长长度。处理 [2, 2, 2] 时，三个 2 都替换第一个位置，答案为 1。如果求最长非递减子序列，才改为寻找第一个严格大于的位置，让相等元素可以接续。

如果要返回具体子序列呢？

动态规划中可以记录每个位置的前驱，从最大 dp 对应位置倒推。二分法则额外维护各长度结尾的原数组下标，以及每个元素接续时的前驱下标；最终沿最长结尾的前驱链回溯，不能直接返回 tails。

能否先排序再求？

不能直接排序原数组，那会改变下标顺序，把问题变成另一道题。例如 [3, 2, 1] 的答案是 1，排序后却变成长度为 3 的递增数组。

参考资料