最长递增子序列
维基百科，自由的百科全书
在计算机科学中，最长递增子序列（longest increasing subsequence）问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。许多与数学、算法、随机矩阵理论、表示论相关的研究都会涉及最长递增子序列。[1]解决最长递增子序列问题的算法最低要求O(n log n)的时间复杂度，这里n表示输入序列的规模。[2]
例子[编辑]
对于以下的原始序列
- 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
最长递增子序列为
- 0, 2, 6, 9, 11, 15.
值得注意的是原始序列的最长递增子序列并不一定唯一，对于该原始序列，实际上还有以下两个最长递增子序列
- 0, 4, 6, 9, 11, 15 或 0, 4, 6, 9, 13, 15
参考文献[编辑]
- ^ Aldous, David; Diaconis, Persi, Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem, Bulletin of the American Mathematical Society, 1999, 36 (04): 413–432, doi:10.1090/S0273-0979-99-00796-X.
- ^ Schensted, C., Longest increasing and decreasing subsequences, Canadian Journal of Mathematics, 1961, 13: 179–191, MR 0121305, doi:10.4153/CJM-1961-015-3.
