返回工具主页

最长递增子序列（动态规划）演示

在一个序列中找出最长的严格递增子序列。本页使用动态规划，逐步填充 dp 数组和 pre 前驱数组，最后回溯得到完整子序列。

时间复杂度：O(n²) | 空间复杂度：O(n)

输入数列

动态规划过程

原数列 dp 长度 前驱 pre
原数列 nums
dp 数组（以当前元素结尾的最长递增子序列长度）
pre 数组（前驱元素下标）
当前 i: - 当前 j: - 最长长度: 1 结尾下标: 0
点击“开始演示”启动动态规划过程。

操作控制

400ms
0
比较次数
0
更新次数

核心代码

nums = [1, 7, 3, 5, 9, 4, 8]
n = len(nums)
dp = [1] * n
pre = [-1] * n
maxlen = 1
maxend = 0
for i in range(1, n):
for j in range(0, i):
if nums[j] < nums[i]:
if dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
pre[i] = j
if dp[i] > maxlen:
maxlen = dp[i]
maxend = i
ans = []
while pre[maxend] != -1:
ans.append(nums[maxend])
maxend = pre[maxend]
ans.append(nums[maxend])
print(ans[::-1])

思路说明：dp[i] 表示以第 i 个元素结尾的最长递增子序列长度。枚举每个前面的元素 j，如果 nums[j] < nums[i]，说明可以把 nums[i] 接在以 nums[j] 结尾的子序列后面，此时尝试更新 dp[i]。pre[i] 记录这个子序列中 nums[i] 前面的元素下标，便于最后回溯输出完整子序列。