最长上升子序列（LIS）——如何在乱序中找出最长的递增“尾巴”

你有没有在体育课上遇到过这种情形：老师让同学们按身高从矮到高排成一队，但队伍已经乱成一团。老师不想让大家全部重新排，而是让一部分同学站出来，按照原来站在队伍里的顺序（从左到右），并且身高要严格递增。你能选出来多少个同学，让他们的身高满足要求？这个问题就是编程里经典的“最长上升子序列”（Longest Increasing Subsequence，简称 LIS）。

简单来说，LIS 就是：给你一串数字，你可以跳着选，但不能改变这些数字的原始顺序，挑出来的数字必须一个比一个大（严格递增），最后找出最长的那个序列有多长。比如数列 [3, 1, 4, 2, 5]，最长上升子序列可以是 [1, 2, 5] 或 [3, 4, 5]，长度都是 3。

下面我们一步步来学习如何用 Python 解决这个问题。

第一个问题：怎么想？“dp” 是什么？

动态规划（Dynamic Programming，简称 DP）是一种把大问题拆成小问题，再把小问题的答案存起来重复使用的技巧。对于 LIS，我们定义一个数组 dp，其中 dp[i] 表示 以第 i 个数字结尾的最长上升子序列的长度。比如对于 nums = [3, 1, 4, 2, 5]，dp[0] 就是以数字 3 结尾的序列长度（就是它自己，长度为 1），dp[1] 是以 1 结尾的（也是 1），dp[2] 是以 4 结尾的（可以接在 3 或 1 后面，最长为 2），等等。

为什么叫“以……结尾”？

因为我们要保证子序列是递增的，所以只能把当前数字接到前面比它小的数字后面。如果不知道前面哪些数字小，就没法确定长度。所以每个位置只关心“以我结尾”的序列最长能有多长。

第二个问题：如何计算出 dp[i]？

对于每个位置 i（从 0 开始），我们都要回头看它前面的所有位置 j（从 0 到 i-1）。只要 nums[j] < nums[i]（前面的数字比当前数字小），那么当前数字就可以接在它后面，形成一个新的更长的序列。这个新序列的长度就是 dp[j] + 1。我们用 max 函数在所有可能的 j 中挑出最大的那个，作为 dp[i] 的候选值。但注意，即使前面没有比它小的数字，它自己也是一个长度为 1 的序列，所以 dp[i] 至少是 1。

一个简单例子：玩身高卡片

假设我们有一排同学的身高（数字）：

[2, 5, 3, 7, 101, 18]

我们记下每个同学的位置（0 到 5）。

第 0 个同学身高 2，前面没人，dp[0] = 1。
第 1 个同学身高 5，前面有 2（比 5 小），所以可以接在后面，dp[1] = max(1, dp[0]+1=2) = 2。
第 2 个同学身高 3，前面有 2（比 3 小），dp[2] = max(1, dp[0]+1=2) = 2。
第 3 个同学身高 7，前面有 2、5、3 都比 7 小，分别能得 2、3、3，最大是 3，所以 dp[3] = 3。
第 4 个同学身高 101，前面有 2、5、3、7 都小，最大是 dp[3]+1=4，所以 dp[4] = 4。
第 5 个同学身高 18，前面比它小的有 2、5、3、7（101 太大不算），最大是 dp[3]+1=4，所以 dp[5] = 4。

最后 dp 数组为 [1, 2, 2, 3, 4, 4]，最大值是 4。所以最长上升子序列长度是 4（比如 [2, 5, 7, 101] 或 [2, 3, 7, 18] 等）。

第三个问题：用代码怎么写？

我们用两层循环来实现：外层循环枚举每个位置 i，内层循环枚举 i 前面的所有位置 j。代码非常清晰：

def length_of_lis(nums):
    # 如果列表为空，直接返回 0
    if not nums:
        return 0
    
    n = len(nums)                     # 数字的个数
    dp = [1] * n                      # 每个数字本身就是一个长度为1的序列，所以先全部赋值为1
    
    for i in range(1, n):             # 从第二个数字开始，因为第一个已经初始化了
        for j in range(0, i):         # 看前面所有的数字
            if nums[j] < nums[i]:     # 如果前面的数字比当前数字小，可以接在后面
                dp[i] = max(dp[i], dp[j] + 1)   # 取最大的那个
    
    return max(dp)                    # dp数组的最大值就是答案

# 测试一下
print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 输出4

代码解释（逐行看）

n = len(nums)：得到数字的总数。
dp = [1] * n：初始化时每个数字单独作为一个序列，长度为 1。
外层 for i 从 1 到 n-1，因为第 0 个已经不用再判断前面的了。
内层 for j 从 0 到 i-1，检查所有前面的数字。
if nums[j] < nums[i] 成立，说明 nums[i] 可以接在 nums[j] 后面，形成更长的序列。
dp[i] = max(dp[i], dp[j] + 1)：取当前 dp[i] 和新的候选值中较大的，保证存储的是最大长度。
最后用 max(dp) 找出所有 dp[i] 中的最大值，那就是整个序列的 LIS 长度。

常见错误（新手容易掉坑）

忘记初始化：dp[0] 必须为 1，不要设成 0。因为每个数字自己就是一个长度为 1 的上升子序列。
条件写反：应该是 nums[j] < nums[i]（前面的比当前小）才能接，如果写成 > 就变成递减了。
忘记取 max：只写 dp[i] = dp[j] + 1 可能会被后面更小的 j 覆盖，必须用 max 保证 dp[i] 保持最大值。
直接用变量名与内置函数冲突：比如用 max 作为变量名会导致后面无法调用内置 max()。建议用 max_len 等。
返回最后一个 dp 值：有的人以为答案就是 dp[n-1]，实际上最长子序列不一定以最后一个数字结尾，所以必须返回整个 dp 数组的最大值。

完整可运行示例（加上测试和打印）

下面是一个完整的 Python 程序，你可以直接复制运行，看看结果：

def length_of_lis(nums):
    """返回列表nums的最长上升子序列长度"""
    if not nums:
        return 0
    
    n = len(nums)                     # 数字个数
    dp = [1] * n                      # 初始化每个位置至少为1
    
    for i in range(1, n):
        for j in range(0, i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

# 测试几个例子
test1 = [3, 1, 4, 2, 5]
print(f"{test1} 的 LIS 长度是 {length_of_lis(test1)}")   # 输出3

test2 = [1, 2, 3, 4, 5]
print(f"{test2} 的 LIS 长度是 {length_of_lis(test2)}")   # 输出5

test3 = [5, 4, 3, 2, 1]
print(f"{test3} 的 LIS 长度是 {length_of_lis(test3)}")   # 输出1

test4 = []
print(f"空列表的 LIS 长度是 {length_of_lis(test4)}")     # 输出0

运行结果：

[3, 1, 4, 2, 5] 的 LIS 长度是 3
[1, 2, 3, 4, 5] 的 LIS 长度是 5
[5, 4, 3, 2, 1] 的 LIS 长度是 1
空列表的 LIS 长度是 0

进阶一点：除了长度，还能得到具体的序列吗？

当然可以！我们只需要额外记录每个位置是从哪里转移来的（比如用一个 parent 数组记录前一个位置），最后倒推回去就能得到具体的子序列。不过那是更进阶的技巧，小同学们先掌握求长度就很棒了。

另外，这个动态规划版本的时间复杂度是 O(n²)（因为两层循环），如果数字很多（比如几万个）可能会慢。更快的办法是使用“贪心 + 二分查找”，可以把复杂度降到 O(n log n)。有兴趣的同学可以去查一下“耐心排序”或者“patience sorting”算法。

最长上升子序列（LIS）——在乱序队伍中找出最长的递增队列