首页路线图题单教程题目可视化错题本进度

加载中…

最长递增子序列 LIS

动态规划：每个位置记录以它结尾的 LIS 长度。

序列:

速度:

[0]31

[1]11

[2]41

[3]11

[4]51

[5]91

[6]21

[7]61

最长递增子序列（LIS）：每个元素自身至少构成长度 1

当前最长 = 1（下标下数字为该位置结尾的 LIS 长度）

步骤 1 / 21最长递增子序列（LIS）：每个元素自身至少构成长度 1

算法代码

当前高亮行: 1(最长递增子序列（LIS）：每个元素自身至少构成长度 1)

1function lis(seq) {

2 lengths = Array(n).fill(1);

3 for (i = 1..n) for (j = 0..i)

4 if (seq[j] < seq[i])

5 lengths[i] = max(lengths[i], lengths[j] + 1);

6 return max(lengths);

7}