最长递增子序列

Longest Increasing Subsequence

动态规划

2025/10/16

思路：动态规划，因为是递增序列，所以一维DP，所以设置两个变量

lengthOfLIS[n] = lengthOfLIS[n-1] + 1 if maxval[n-1]< a[n] else maxval[n] = a[n] if lengthOfLIS[n] > lengthOfLIS[n-1] else maxval[n-1]

评价：公式错了。一维DP不一定是两个变量，也有可能是多个step。

推荐思路：设以 a[n] 为结尾的最长递增子序列长度为 L[n]，则 L[n] = 1 + max(L[j]) (j在n前面且a[j]比a[n]小)。最后取L[i]的max

Back to top