最長的子序列基本資訊
在最長遞增子問題是要找到從給輸入序列，其中序列中的元素以最低的排序，以最高等級序列。所有子序列都不是連續的或唯一的。
最長增長子序列的應用：
最長增加子序列，最長公共子序列等演算法用於 Git 等版本控制系統。
簡單形式的演算法：
- 查詢兩個文件共有的唯一行。
- 從第一個文件中取出所有這些行，並根據它們在第二個文件中的外觀進行排序。
- 計算結果序列的 LIS（通過耐心排序 ），獲得最長的匹配行序列，兩個文件的行之間的對應關係。
- 在已經匹配的行之間的每個行範圍上遞迴演算法。
現在讓我們考慮一個更簡單的 LCS 問題示例。這裡，輸入只是一個不同整數 a1,a2,...,an. 的序列，我們希望找到其中最長的增長子序列。例如，如果輸入是 **7,3,8,4,2,6，**那麼最長的增加子序列是 3,4,6 。
最簡單的方法是按遞增順序對輸入元素進行排序，並將 LCS 演算法應用於原始和排序的序列。但是，如果檢視結果陣列，你會注意到許多值是相同的，並且陣列看起來非常重複。這表明 LIS（增長最長的子序列）問題可以使用僅使用一維陣列的動態程式設計演算法來完成。
虛擬碼：
- 描述我們想要計算的值陣列。
對於1 <= i <= n，設A(i)是增長最長的輸入序列的長度。請注意，我們最終感興趣的長度是max{A(i)|1 ≤ i ≤ n}。 - 再次發生。
對於1 <= i <= n，A(i) = 1 + max{A(j)|1 ≤ j < i和input(j) <input(i)}. - 計算 A 的值。
- 找到最佳解決方案。
以下程式使用 A 來計算最佳解決方案。第一部分計算值 m，使得 A(m) 是輸入的最佳增加子序列的長度。第二部分計算最佳增加子序列，但為方便起見，我們以相反的順序列印出來。該程式在時間 O(n) 內執行，因此整個演算法在時間 O（n ^ 2）內執行。
第 1 部分：
m ← 1
for i : 2..n
if A(i) > A(m) then
m ← i
end if
end for
第 2 部分：
put a
while A(m) > 1 do
i ← m−1
while not(ai < am and A(i) = A(m)−1) do
i ← i−1
end while
m ← i
put a
end while
遞迴解決方案：
方法 1：
LIS(A[1..n]):
if (n = 0) then return 0
m = LIS(A[1..(n − 1)])
B is subsequence of A[1..(n − 1)] with only elements less than a[n]
(* let h be size of B, h ≤ n-1 *)
m = max(m, 1 + LIS(B[1..h]))
Output m
方法 1 中的時間複雜度： O(n*2^n)
方法 2：
LIS(A[1..n], x):
if (n = 0) then return 0
m = LIS(A[1..(n − 1)], x)
if (A[n] < x) then
m = max(m, 1 + LIS(A[1..(n − 1)], A[n]))
Output m
MAIN(A[1..n]):
return LIS(A[1..n], ∞)
方法 2 中的時間複雜性： O(n^2)
方法 3：
LIS(A[1..n]):
if (n = 0) return 0
m = 1
for i = 1 to n − 1 do
if (A[i] < A[n]) then
m = max(m, 1 + LIS(A[1..i]))
return m
MAIN(A[1..n]):
return LIS(A[1..i])
方法 3 中的時間複雜性： O(n^2)
迭代演算法：
以自下而上的方式迭代計算值。
LIS(A[1..n]):
Array L[1..n]
(* L[i] = value of LIS ending(A[1..i]) *)
for i = 1 to n do
L[i] = 1
for j = 1 to i − 1 do
if (A[j] < A[i]) do
L[i] = max(L[i], 1 + L[j])
return L
MAIN(A[1..n]):
L = LIS(A[1..n])
return the maximum value in L
迭代方法的時間複雜度： O(n^2)
輔助空間： O(n)
讓我們以 { 0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15 } 作為輸入。因此，給定輸入的最長增加子序列是 {0,2,6,9,11,15} 。