最长上升子序列的最优算法
1 问题背景最长上升子序列问题
(Longest Increasing Subsequence)
(Dynamic
在
算法教学中的经典问题，在学习动态规划
Programming)相关内容时经常出现。在动态规划这一章节中出现的频率只比最长公共子序列
(Longest Common
Sequence)小。最长上升子序列问题的动态规划解法的时间复杂度为n2，而我们可以得到的最长上升子序列的最优化算法的复杂度为
nlogn。最长上升子序列在我们的课程中是作
为动态规划的联系来做的，这样就误导了大家，使得大家认为最长上升子序列问题的最优算法就是动态规划算法。这样就违背另外算法研究的精神，问题描述
设A=1,x2,··· ,xn >n个不等的整数构成的序列，是单调递增子序列xi1,xi2,i1,xi2,
··· ,xik >i1 2 使得··· kxi1 i2 ，且··· ,xik >
···k.子序列 i
A的一个
所以我写这篇文章，以正视听。
的长度是含有的整数个数k.例如A
=1,5,3,8,10,6,4,9 >,1,5,8,10 >,1,5,8,9 >,
他的长为4的递增子序列是：
···.设计一个算法求A的一个最长的单调
.
递增子序列，分析算法的时间复杂度3 算法思想
设A[t]表示序列中的第t个数F[t]表示从1到tt这一段中以t
F[t] = 0(t = 1,2,
··· ,len(A))
结尾的最长上升子序列的长度有动态规划方程1,且A[j] [t]).
现在，我们仔细考虑计算且A[y]满足一下情况.
。则
F[t] = max1,F[j] + 1(j = 1,2,...,t ?
F[t]时的情况。假设有两个元素A[x]
x A[x] [y] [t] F[x] = F[y]
此时，选择A[x]和选择A[y]都可以得到同样的在最长上升子序列的这个位置中，应该选择
F[t]值，那么，A[x]还是A[y]
(2)，在
很明显，选择A[x]比选择A[y]要好。因为由于条件A[x + 1]
···A[t ? 1]
这一段中，如果存在A[z]?A[x] [z] [y]，则与
再根据条件(3)，
F[]的每
选择A[y]相比，将会得到更长的上升子序列。我们会得到一个启示：根据
F[]的值进行分类。对于
一个取值k，我们只需要保留满足小值。设D[k]记录这个值，即注意到D[]的两个特点：
F[t] = k的所有A[t]中的最
。
D[k] = minA[t](F[t] = k)
D[i]的值是在整个计算过程中是单调下降的。
D[]的值是有序的，即D[k] [k + 1]。
利用D[]，我们可以得到另外一种计算最长上升子序列长度的方法。设当前已经求出的最长上升子序列长度为
len。我们利用t来遍历A[]，如果
A[t]?D[len],则我们将A[t]接在D[len]后面，这样我们就得到了一个更长的上升子序列。此时更新A[t]；否则在D[1],D[2],
len = len + 1，D[len] =
中寻找最小的j，使得D[j] >
A[]后，len
··· ,D[len]
A[t],将D[j]更新为A[t],其他不变。最后遍历完整个就是A[]中最长上升子序列的长度。4 算法正确性的证明
我们用数学归纳法来证明这个算法的确返回了升子序列的长度。归纳命题如下
A[]中最长上
:对于1 ≤ t ≤ n,当我们处理
最长上升子序列的长度。··· ,A[t]
中所有长度为i
完A[t]时，len是A[1],A[2],··· ,A[t]且对于1 ≤ i ≤ lenD[i]，则是A[1],A[2],的上升序列的的最后一个数的最小值。
归纳基础: 当t = 1时，len = 1,D[1] = A[1]命题显然成立。归纳假设:如果当t = j时归纳命题成立，则我们现在来处理A[j + 1]。
如果A[j + 1] > D[len]，根据归纳假设，A[1],A[2],,A[j]··· 中最
最长上升子序列的最优算法
