第54课 - 最长递增子序列（Longest Increasing Subsequence）

学习目标

理解什么是最长递增子序列（LIS）问题
掌握使用动态规划求解LIS的方法
学会使用贪心+二分查找的优化解法
能够比较两种方法的时间复杂度并选择合适的算法
掌握LIS问题的变种处理

核心概念

最长递增子序列（LIS）是指在序列中找出一个最长的子序列，使得子序列中的元素严格递增，但不需要连续。

举个例子：

原始序列：[10, 9, 2, 5, 3, 7, 101, 18]
最长递增子序列之一：[2, 3, 7, 101] 或 [2, 3, 7, 18]（长度为4）

动态规划解法（基础）

我们用 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。

状态转移方程：

dp[i] = max(dp[j] + 1)  其中 j < i 且 nums[j] < nums[i]

如果找不到这样的 j，则 dp[i] = 1（只有自己）

贪心 + 二分查找解法（优化）

这种方法更高效：

维护一个数组 tails，其中 tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素
遍历原数组时，用二分查找在 tails 中找到第一个大于等于当前元素的位置并替换
如果当前元素比所有元素都大，就添加到 tails 末尾

代码示例

1. 动态规划解法 O(n²)

def length_of_lis_dp(nums):
    """
    动态规划求解最长递增子序列长度
    :param nums: List[int] 输入序列
    :return: int 最长递增子序列长度
    """
    if not nums:
        return 0
    
    n = len(nums)
    # dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
    dp = [1] * n  # 每个元素自己就是一个长度为1的子序列
    
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                # 如果 nums[j] < nums[i]，则可以将 nums[i] 接在以 nums[j] 结尾的子序列后面
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

# 测试
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(f"序列: {nums}")
print(f"LIS长度（动态规划）: {length_of_lis_dp(nums)}")  # 输出: 4

2. 贪心 + 二分查找解法 O(n log n)

def length_of_lis_binary_search(nums):
    """
    贪心+二分查找求解最长递增子序列长度
    :param nums: List[int] 输入序列
    :return: int 最长递增子序列长度
    """
    if not nums:
        return 0
    
    # tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素
    tails = []
    
    for num in nums:
        # 二分查找第一个大于等于 num 的位置
        left, right = 0, len(tails)
        while left < right:
            mid = (left + right) // 2
            if tails[mid] < num:
                left = mid + 1
            else:
                right = mid
        
        # 如果 left 等于 tails 的长度，说明 num 比所有元素都大
        if left == len(tails):
            tails.append(num)
        else:
            tails[left] = num  # 替换，保持 tails 的最优性
    
    return len(tails)

# 测试
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(f"序列: {nums}")
print(f"LIS长度（二分查找）: {length_of_lis_binary_search(nums)}")  # 输出: 4

3. 获取具体的LIS序列

def find_lis_sequence(nums):
    """
    获取具体的最长递增子序列（使用动态规划+回溯）
    :param nums: List[int] 输入序列
    :return: List[int] 最长递增子序列
    """
    if not nums:
        return []
    
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n  # 记录前一个元素的索引，用于回溯
    
    # 计算dp数组
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                prev[i] = j
    
    # 找到最长子序列的最后一个元素的索引
    max_len = max(dp)
    max_index = dp.index(max_len)
    
    # 回溯构造子序列
    lis = []
    while max_index != -1:
        lis.append(nums[max_index])
        max_index = prev[max_index]
    
    return lis[::-1]  # 反转得到正确的顺序

# 测试
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(f"序列: {nums}")
lis = find_lis_sequence(nums)
print(f"一个LIS序列: {lis}")  # 输出: [2, 3, 7, 101] 或 [2, 3, 7, 18]
print(f"长度: {len(lis)}")     # 输出: 4

实践练习

练习1：基础计算（易）

给定序列 [0, 1, 0, 3, 2, 3]，使用动态规划方法计算最长递增子序列的长度。

预期输出：4（序列为 [0, 1, 2, 3]）

练习2：二分查找方法（中）

使用贪心+二分查找方法，计算序列 [7, 7, 7, 7, 7, 7, 7] 的最长递增子序列长度。

预期输出：1（注意：递增要求严格递增）

练习3：输出所有LIS（难）

给定序列 [1, 3, 6, 7, 9, 4, 10, 5, 6]，输出所有长度最长的递增子序列（如果有多个的话）。

提示：需要修改回溯算法，使用DFS搜索所有可能的路径。

常见错误

1. 混淆"递增"和"非递减"

# 错误：允许相等元素
if nums[j] <= nums[i]:  # 这是"非递减"，不是"递增"
    dp[i] = max(dp[i], dp[j] + 1)

# 正确：严格递增
if nums[j] < nums[i]:  # 注意是 < 而不是 <=
    dp[i] = max(dp[i], dp[j] + 1)

2. 动态规划中忘记初始化

# 错误：dp数组未初始化
dp = []  # 这样会导致索引错误

# 正确：每个元素至少是长度为1的子序列
dp = [1] * n

3. 二分查找边界错误

# 错误：二分查找范围错误
left, right = 0, len(tails) - 1

# 正确：搜索整个数组，包括末尾位置
left, right = 0, len(tails)  # 注意是右开区间

4. 忘记回溯时数组越界

# 错误：直接使用max_index，可能为-1
while max_index >= 0:
    lis.append(nums[max_index])
    max_index = prev[max_index]  # 当max_index为0时，prev[0]可能是-1

# 正确：检查前一个索引是否有效
while max_index != -1:  # 使用-1作为终止条件
    lis.append(nums[max_index])
    max_index = prev[max_index]

小结

关键要点回顾

LIS定义：在序列中找最长的严格递增子序列（不要求连续）
动态规划解法：
- 状态：dp[i] 表示以 nums[i] 结尾的LIS长度
- 转移：dp[i] = max(dp[j] + 1) 对于所有 j < i 且 nums[j] < nums[i]
- 时间复杂度：O(n²)，空间复杂度：O(n)
贪心+二分查找解法：
- 维护一个 tails 数组记录最优末尾元素
- 使用二分查找快速定位插入位置
- 时间复杂度：O(n log n)，空间复杂度：O(n)
变种处理：
- 要输出具体序列时，需要额外记录前驱信息
- 如果是"非递减"，需要修改比较条件为 <=
选择策略：
- 序列长度较小时（n ≤ 1000），两种方法都可以
- 序列长度较大时（n > 1000），优先使用二分查找方法

下一步学习建议

理解LIS与最长公共子序列（LCS）的关系
尝试解决LIS的变种问题，如最长递增路径
学习如何将LIS应用于实际问题，如信封嵌套问题

练习编辑器

rust