算法基础-最长递增子序列

作为一个菜鸟,本文作为查询模板

【问题1】最长递增子序列问题
【问题描述】设L=<a1,a2,…,an>是n个不同的实数的序列,L的递增子序列是这样一个子序列Lin=<ak1,ak2,…,akm>,其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。
采用一个数组temp[]保存 以当前元素结尾的最长递增子序列长度,最后求出全局最优解
更新最长递增子序列的条件:a[i]>a[j] (i>j) 且前一个递增序列长度大于等于当前递增序列长度

动态规划:

 

代码(不重复的子序列)

几个解释得较好的链接,供学习用:

http://blog.csdn.net/u013074465/article/details/45442067

http://blog.csdn.net/joylnwang/article/details/6766317

读者评分
[评分人数: 0 平均分: 0]

评论

OmegaXYZ