最長遞增子序列
維基百科，自由的百科全書
在計算機科學中，最長遞增子序列（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.
