数据结构与算法 / 系统课时
求解最长递增子序列问题
求解最长递增子序列问题
最长递增子序列要求从原数组中选出若干元素,保持原有相对顺序但允许跳过元素。关键不是比较相邻位置,而是为每个位置枚举所有可能的合法前驱,并保存“以当前位置结尾”的最优长度。
学习目标
- 定义以某个元素结尾的最长递增子序列状态
- 通过枚举所有合法前驱推导 动态规划解法
- 理解子序列与连续子数组的区别,以及为什么不能只检查相邻元素
状态要绑定到结尾位置
给定数组 nums,定义 dp[i] 为:必须选择 nums[i] 作为最后一个元素时,最长严格递增子序列的长度。
这个定义非常重要。若只定义“前 i 个元素中的最长长度”,就不知道当前最优序列最后一个值是多少,因此无法判断 nums[i] 能否接到它后面。
任何单独一个元素都能构成长度为 1 的递增子序列,所以初始值统一为:
接下来只需要寻找能够接到 nums[i] 前面的元素。
枚举所有合法前驱
对于位置 i,所有满足 j < i 且 nums[j] < nums[i] 的位置 j 都可能成为前驱。如果选择了某个前驱,那么以 i 结尾的长度就是 dp[j] + 1。
因此转移为:
以 [10, 9, 2, 5, 3, 7, 101, 18] 为例,处理到元素 7 时,前面的 2、5、3 都比 7 小。其中以 5 或 3 结尾的最优长度已经是 2,所以 dp[5] 可以更新为 3,对应子序列 [2, 5, 7] 或 [2, 3, 7]。
最终答案不是固定的 dp[n - 1],因为最长递增子序列未必以数组最后一个元素结尾,而是整个 dp 数组的最大值。
完整二次复杂度实现
下面直接按照状态定义实现。外层循环确定结尾 i,内层循环枚举它之前的所有候选前驱 j。
def length_of_lis(nums: list[int]) -> int:
if not nums:
return 0
dp = [1] * len(nums)
for i in range(len(nums)):
# 枚举所有更早的位置,而不是只看 nums[i - 1]。
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(length_of_lis(nums))预期输出
4一种长度为 4 的递增子序列是 [2, 3, 7, 18]。程序只计算长度,因此不会输出具体序列;如果题目要求恢复路径,还需要额外保存每个位置选择的前驱。
为什么不能只比较相邻元素
子序列允许跳过元素,因此有效前驱可能离当前位置很远。例如数组 [1, 5, 2, 3, 4] 中,最长递增子序列是 [1, 2, 3, 4]。元素 2 虽然比它左边紧邻的 5 小,却仍然可以接在更早的 1 后面。
如果只比较 nums[i - 1] 与 nums[i],得到的其实更接近连续递增片段问题,而不是最长递增子序列。LIS 的核心动作始终是:对每个结尾位置,检查所有更早且数值更小的位置。
复杂度与状态设计边界
共有 n 个结尾位置,每个位置最多检查前面的 n - 1 个元素,所以时间复杂度是 ;dp 数组占用 额外空间。
这个解法最值得掌握的是“以某个位置结尾”的状态设计。很多子序列问题之所以不能像连续数组那样只看相邻元素,正是因为一次选择可以跨过任意多个位置。只要下一步是否合法取决于此前选中的最后一个元素,把状态绑定到结尾位置通常就是自然的建模起点。