问题
序列s的递增子序列是原序列的子集,元素相对原序列的顺序不变,且依次递增。例如序列s=[3,0,2,1,4]的递增子序列有
[],[3],[0],[2],[1],[4],[3,4],[0,2],[0,4],[2,4],[1,4],[0,2,4],[0,1,4] 求序列s的最长递增子序列的长度。
解法
设序列s的长度为n,范围为[1,n]。设f(i)是以s[i]为最后一个元素的最长递增子序列的长度,则有状态转移方程:
f(i)={0max{f(k)+1}(initialize)(loop)i=0i∈[1,n],k∈[1,i−1],s[i]>s[k] (1) 前0个字符s[0]的最长递增子序列显然是空的,因此f(0)=0;
(3) 对于序列s中第i个数字s[i],至少s[i]一个字符可以作为一个递增子序列,因此至少有f(i)≥1。若s[i]>s[k](其中k∈[1,i−1])则s[i]与s[1,k]的最长递增子序列可以组成一个更长的递增子序列,因此f(i)=f(k)+1,遍历所有可能的k,找出下一个最长的递增子序列;
该算法的时间复杂度为O(n2)。
源码
LongestIncreasingSubsequence.h
LongestIncreasingSubsequence.cpp
测试
LongestIncreasingSubsequenceTest.cpp