温婉毛巾

文章
4
资源
0
加入时间
3年0月20天

最长递增子序列(LIS)

转载自点击打开链接最长递增子序列也叫做最长上升子序列。嘿嘿,既然都是子序列,就和LCS中一样,元素不用必须是连续的。题:求一个一维数组arr[i]中的最长递增子序列的长度,如在序列1,-1,2,-3,4,-5,6,-7中,最长递增子序列长度为4,可以是1,2,4,6,也可以是-1,2,4,6。方法一:DP像LCS一样,从后向前分析,很容易想到,第i个元素之前