最长递增子序列

  • A+
所属分类:算法与数据结构

问题

我们有一个数字序列包含n个不同的数字,如何求出这个序列中的最长递增子序列长度?比如2, 9, 3, 6, 5, 1, 7这样一组数字序列,它的最长递增子序列就是2, 3, 5, 7,所以最长递增子序列的长度是4

思考过程

符合“一个模型三个特征”,可以使用动态规划。

回溯法求解

画出状态图

最长递增子序列

在画状态图时发现,有很多重复状态,上一状态重复,则此状态之下的状态全部重复,所以回溯法效率很低。同时也很显然,当上一数字相同时,maxLen只会出现在len最大的分支上,因此,只需保存每一数字的最大长度即可。

动态规划代码

打印此递增序列

 

许龙涛

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: