最长的子序列基本信息
在最长递增子问题是要找到从给输入序列，其中序列中的元素以最低的排序，以最高等级序列。所有子序列都不是连续的或唯一的。
最长增长子序列的应用：
最长增加子序列，最长公共子序列等算法用于 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} 。