如何求最长递增子序列（LIS）的长度？

直接回答：两种解法。1）DP：dp[i] 表示以 nums[i] 结尾的 LIS 长度，dp[i] = max(dp[j] + 1)（j < i 且 nums[j] < nums[i]），时间 O(n²)。2）贪心 + 二分：维护数组 tails，tails[k] 表示长度为 k+1 的递增子序列的最小结尾；遍历每个数，二分找到 tails 中第一个 ≥ 它的位置替换（或追加），tails 的长度即答案，时间 O(n log n)。

展开解析：贪心解的正确性依赖一个观察：相同长度下结尾越小，未来可扩展空间越大，所以总是尽量压低每个长度的结尾值；tails 本身保持严格递增，因此可以二分。注意 tails 数组不是真实的 LIS（替换会破坏链），只能得到长度，要输出序列得回退到 DP 并记录前驱。经典变体：俄罗斯套娃信封（先按一维排序、另一维做 LIS，注意同宽时高要降序）、最长链对、以及「不下降」与「严格递增」的差别决定二分找 lower_bound 还是 upper_bound。追问方向：LIS 与最长公共子序列（LCS）的转化（对排列把元素映射为下标后求 LIS）、耐心排序（patience sorting）视角。

示例：

from bisect import bisect_left

def length_of_lis(nums):
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)