一种求所有最长增量子序列的算法

An algorithm for computing the all longest increasing subsequence

对计算最长增量子序列(longest increasing subsequence,LIS)的CM(Cover-Making)算法进行详细地分析,提出一个基于CM算法的新算法,可以求出一个序列的所有最长增量子序列。它的时间复杂度是O((m+1)k+(n-k)logk),空间复杂度是O(n+km)。

The Cover-Making（CM） algorithm of the longest increasing subsequence was analyzed, and a new algorithm that can compute a sequence＇ s all longest increasing subsequences was presented, based on the CM algorithm. The complexity of the time is O（ （m ＋ 1 ）k ＋ （n- k）log k） and the complexity of the space is O（ n ＋ km）.