Part 5.2：最长上升子序列 (LIS)

引言：寻找股价的“上升趋势”

想象一下，你是一位股票分析师，拿到了一支股票连续 N 天的收盘价序列，例如 [10, 9, 2, 5, 3, 7, 101, 18]。你的老板想知道，在这段时间里，最长的“持续上涨”周期有多长？

这里的“持续上涨”并不是指连续几天的上涨，而是指你可以从这个序列中挑选出任意多个交易日，只要它们的时间顺序保持不变，且价格一路走高。例如，你可以挑选第 3 天 (价格 2)、第 4 天 (价格 5)、第 6 天 (价格 7)、第 7 天 (价格 101)，形成一个长度为 4 的上涨序列 [2, 5, 7, 101]。

这个问题，就是算法领域中著名的最长上升子序列 (Longest Increasing Subsequence, LIS) 问题。

为什么 LIS 如此重要？

  • 面试价值：LIS 是 DP 问题中的常青树，几乎是所有一线大厂面试的必考题型。它不仅考察基础的 DP 思维，其 O(n log n) 的优化解法更能区分候选人的思维深度，是展现算法优化能力的绝佳舞台。
  • 学术与工程价值：LIS 模型在很多领域都有应用，如生物信息学中的 DNA 序列分析、数据挖掘中的模式识别、以及各种组合优化问题。它也是许多更复杂算法问题的基础（如“俄罗斯套娃信封问题”）。

本文将带你从最直观的 O(n²) DP 解法开始，一步步揭示其瓶颈，并最终引出结合了贪心和二分查找的 O(n log n) 高效解法，让你彻底征服 LIS。

背景知识：子序列 vs. 子串

在开始之前，我们必须明确一个核心概念：子序列 (Subsequence) 和 子串 (Substring) 的区别。

  • 子串：必须是原序列中连续的一部分。例如，[2, 5, 3] 是 [10, 9, 2, 5, 3, 7, 101, 18] 的一个子串。
  • 子序列：可以不连续，但必须保持原有的相对顺序。例如，[2, 5, 7, 101] 是原序列的一个子序列，但不是子串。

LIS 求解的是子序列，而不是子串，这给了我们更大的选择自由度。

解法一：O(n²) 动态规划——朴素而强大

这是解决 LIS 问题最经典、最容易想到的 DP 方法。如果你在面试中能写出这个解法，已经证明你具备了基本的 DP 思维。

1. 算法的“直觉”：站在巨人的肩膀上

假设我们要计算以 nums[i] 这个数结尾的最长上升子序列的长度。我们应该怎么做？

一个自然的想法是：向前看。我们遍历 nums[i] 之前的所有数字 nums[j] (其中 j < i)。

  • 如果 nums[j] 比 nums[i] 小，这意味着 nums[i] 可以接在以 nums[j] 结尾的某个上升子序列的后面，形成一个更长的上升子序列。
  • 我们想让这个新的子序列尽可能长，所以我们应该在所有满足 nums[j] < nums[i] 的 j 中，找到那个拥有最长上升子序列的 nums[j]，然后把它“继承”过来，长度再加 1。

例如，对于序列 [... , 2, 5, 3, 7]，当计算以 7 结尾的 LIS 时：

  • 7 > 2，可以接在以 2 结尾的 LIS 后面。
  • 7 > 5，可以接在以 5 结尾的 LIS 后面。
  • 7 > 3，可以接在以 3 结尾的 LIS 后面。

我们只需要比较 len(LIS_ending_with_2), len(LIS_ending_with_5), len(LIS_ending_with_3) 这三个长度，取其中最大的，然后加 1，就是以 7 结尾的 LIS 长度。

2. 严谨原理：状态定义与状态转移方程

  • 状态定义：dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度。

    ⚠️ 注意：这个定义至关重要！dp[i] 必须是以 nums[i] 结尾，而不是指前 i 个数中的 LIS 长度。

  • 状态转移方程：
    对于每个 i，我们需要遍历所有 j < i：
    如果 nums[j] < nums[i]，则 nums[i] 可以接在以 nums[j] 结尾的上升子序列后面。此时，我们有一个长度为 dp[j] + 1 的上升子序列。
    我们需要在所有可能的 j 中找到最大的 dp[j]。
    因此，状态转移方程为：
    **dp[i] = max(dp[j] + 1)**，其中 0 ≤ j < i 且 nums[j] < nums[i]。

  • **初始化 (Base Case)**：
    dp 数组的所有元素都初始化为 1。因为任何一个数字本身都可以构成一个长度为 1 的上升子序列。

  • 最终结果：
    dp 数组中的最大值就是整个序列的 LIS 长度。因为 LIS 必然以序列中的某个数字结尾。

3. 动画式案例

让我们用序列 nums = [10, 9, 2, 5, 3, 7] 来模拟这个过程。

初始化: dp = [1, 1, 1, 1, 1, 1]

  1. i = 0 (nums[0]=10): dp[0] = 1

  2. i = 1 (nums[1]=9): 向前看，没有比 9 小的数。dp[1] = 1

  3. i = 2 (nums[2]=2): 向前看，没有比 2 小的数。dp[2] = 1

  4. i = 3 (nums[3]=5): 向前看…

    • j=2, nums[2]=2 < 5。可以更新 dp[3] = max(dp[3], dp[2]+1) = max(1, 1+1) = 2。
    • dp 变为 [1, 1, 1, 2, 1, 1]

  5. i = 4 (nums[4]=3): 向前看…

    • j=2, nums[2]=2 < 3。可以更新 dp[4] = max(dp[4], dp[2]+1) = max(1, 1+1) = 2。
    • dp 变为 [1, 1, 1, 2, 2, 1]

  6. i = 5 (nums[5]=7): 向前看…

    • j=2, nums[2]=2 < 7。dp[5] = max(1, dp[2]+1) = 2。
    • j=3, nums[3]=5 < 7。dp[5] = max(2, dp[3]+1) = max(2, 2+1) = 3。
    • j=4, nums[4]=3 < 7。dp[5] = max(3, dp[4]+1) = max(3, 2+1) = 3。
    • dp 变为 [1, 1, 1, 2, 2, 3]

最终 dp 数组: [1, 1, 1, 2, 2, 3]
最终结果: max(dp) = 3。LIS 长度为 3 (例如 [2, 5, 7] 或 [2, 3, 7])。

4. Python 实现 (O(n²))

def length_of_lis_n2(nums):
    if not nums:
        return 0
    
    n = len(nums)
    # dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度
    dp = [1] * n

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

    return max(dp)

# --- 案例测试 ---
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(f"O(n^2) 解法, LIS 长度: {length_of_lis_n2(nums)}") # 输出: 4

5. 复杂度分析

  • 时间复杂度: O(n²)。因为我们有两层嵌套循环，每层都与 n 相关。
  • 空间复杂度: O(n)。因为我们需要一个 dp 数组来存储中间状态。

解法二：O(n log n) 贪心 + 二分查找——精妙的优化

O(n²) 的解法在 n 较大时（如 n > 5000）会超时。有没有更高效的方法？答案是肯定的。

1. 算法的“直觉”：让上升子序列“更有潜力”

想象一下，我们正在构建多个不同长度的上升子序列。假设我们有两个长度为 3 的上升子序列：

  • A = [10, 20, 30]
  • B = [1, 2, 3]

现在来了一个新数字 4。它可以接在 B 后面形成 [1, 2, 3, 4]，但不能接在 A 后面。显然，B 比 A “更有潜力”，因为它结尾的数字更小，更容易接纳后续的新数字。

核心思想：如果我们想让上升子序列尽可能长，我们就希望它上升得尽可能缓慢。也就是说，对于相同长度的上升子序列，我们只关心那个结尾数字最小的。

基于这个思想，我们维护一个数组 tails，其中 tails[i] 存储的是所有长度为 i+1 的上升子序列中，结尾数字的最小值。

2. 严谨原理：tails 数组的维护

  • 状态定义：tails 是一个有序数组，tails[i] 表示长度为 i+1 的 LIS 的最小结尾值。

  • 算法流程：
    我们遍历原数组 nums 中的每个数字 num。

    1. 如果 num 比 tails 数组中所有数字都大，说明 num 可以接在最长的那个 LIS 后面，形成一个更长的 LIS。我们直接将 num 追加到 tails 数组末尾。这使 LIS 的长度增加了 1。
    2. 如果 num 在 tails 数组的某个范围内，说明它不能延长当前的 LIS。但是，它有可能优化某个长度的 LIS。我们找到 tails 数组中第一个大于或等于 num 的数字 tails[i]，并用 num 替换它。这相当于我们找到了一个同样长度为 i+1，但结尾更小（更有潜力）的上升子序列。

由于 tails 数组始终保持有序，查找“第一个大于或等于 num 的数字”这个操作，可以用二分查找来高效完成。

3. 动画式案例

nums = [10, 9, 2, 5, 3, 7, 101, 18]
tails = []

  1. num = 10: tails 为空，追加。tails = [10]
  2. num = 9: tails 中第一个 >=9 的是 10。替换。tails = [9]
  3. num = 2: tails 中第一个 >=2 的是 9。替换。tails = [2]
  4. num = 5: 5 > 2，追加。tails = [2, 5]
  5. num = 3: tails 中第一个 >=3 的是 5。替换。tails = [2, 3]
  6. num = 7: 7 > 3，追加。tails = [2, 3, 7]
  7. num = 101: 101 > 7，追加。tails = [2, 3, 7, 101]
  8. num = 18: tails 中第一个 >=18 的是 101。替换。tails = [2, 3, 7, 18]

遍历结束，tails 数组的长度为 4。所以 LIS 的长度为 4。

⚠️ 重要易错点：最终的 tails 数组 [2, 3, 7, 18] 不是 LIS 本身！真正的 LIS 之一是 [2, 3, 7, 101]。tails 数组只保证了其长度是正确的。

4. Python 实现 (O(n log n))

def length_of_lis_nlogn(nums):
    if not nums:
        return 0
    
    # tails[i] 存储长度为 i+1 的 LIS 的最小结尾值
    tails = []

    for num in nums:
        # 二分查找：在 tails 中找到第一个 >= num 的位置
        left, right = 0, len(tails)
        while left < right:
            mid = (left + right) // 2
            if tails[mid] < num:
                left = mid + 1
            else:
                right = mid
        
        if left == len(tails):
            # num 比所有 tails 中的数都大，追加
            tails.append(num)
        else:
            # 替换
            tails[left] = num
            
    return len(tails)

# --- 案例测试 ---
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(f"O(n log n) 解法, LIS 长度: {length_of_lis_nlogn(nums)}") # 输出: 4

5. 复杂度分析

  • 时间复杂度: O(n log n)。外层循环遍历 n 个数字，内层是一个二分查找，其时间复杂度为 log k，其中 k 是 tails 数组的当前长度 (k <= n)。所以总时间复杂度是 O(n log n)。
  • 空间复杂度: O(n)。tails 数组最长可能为 n。

总结

最长上升子序列 (LIS) 是一个完美的例子，展示了如何从一个朴素的 DP 解法，通过深入思考和巧妙的观察，优化到一个更高效的算法。

本文核心要点

✅ O(n²) 解法 (基础 DP)

  • 核心：dp[i] 表示以 nums[i] 结尾的 LIS 长度。
  • 转移：dp[i] = max(dp[j] + 1) for j < i and nums[j] < nums[i]。
  • 优点：思路直观，易于理解和实现。

✅ O(n log n) 解法 (贪心 + 二分)

  • 核心：维护一个 tails 数组，tails[i] 是长度为 i+1 的 LIS 的最小结尾值。
  • 策略：对于新数字 num，如果它能延长 LIS 就追加，否则就去“优化”某个已有长度的 LIS，让其结尾更小。
  • 优点：效率极高，是解决 LIS 问题的标准解法。
  • 注意：tails 数组本身不是 LIS。

掌握了这两种方法，尤其是 O(n log n) 的解法，你在面试中遇到 LIS 及其变种问题时，将能游刃有余。在下一篇文章中，我们将探讨另一个经典的 DP 问题——**最长公共子序列 (LCS)**。