CC++ & Algorithm
算法可视化
入门执行逻辑

最长上升子序列 LIS

dp[i] = 以 a[i] 结尾的最长上升子序列长度。对每个 i,看前面所有比它小的 j,取 dp[j]+1 的最大值。

main.cpp第 2 行
1// LIS: dp[i] = 以 a[i] 结尾的最长上升子序列长度
2int a[] = {3, 1, 4, 1, 5, 9, 2, 6};
3for (int i = 0; i < n; i++) {
4 dp[i] = 1;
5 for (int j = 0; j < i; j++)
6 if (a[j] < a[i])
7 dp[i] = max(dp[i], dp[j] + 1);
8}
9// 答案: max(dp) = 4
变量表1 个变量
a[3, 1, 4, 1, 5, 9, 2, 6]
数组 a
比较交换已就位
i▼j▼
3
0
1
1
4
2
1
3
5
4
9
5
2
6
6
7
1/56

数组 a = [3, 1, 4, 1, 5, 9, 2, 6],求最长上升子序列长度

1 / 56