最长单调子序列（O(n^2) 和 O(nlogn) 算法）

傷城~ 2022-09-18 00:52 5阅读 0赞

**经典的O(n^2)的动态规划算法**

设A\[i\]表示序列中的第i个数，F\[i\]表示从1到i这一段中以i结尾的最长上升子序列的长度，初始时设F\[i\] = 0(i = 1, 2, ..., len(A))。则有动态规划方程：F\[i\] = max\{1, F\[j\] + 1\} (j = 1, 2, ..., i - 1, 且A\[j\] < A\[i\])。

**O(nlogn)算法**

现在，我们仔细考虑计算F\[i\]时的情况。假设有两个元素A\[x\]和A\[y\]，满足

(1)x < y < i

(2)A\[x\] < A\[y\] < A\[i\]

(3)F\[x\] = F\[y\]

此时，选择F\[x\]和选择F\[y\]都可以得到同样的F\[i\]值，那么，在最长上升子序列的这个位置中，应该选择A\[x\]还是应该选择A\[y\]呢？

很明显，选择A\[x\]比选择A\[y\]要好。因为由于条件(2)，在A\[x+1\] ... A\[i-1\]这一段中，如果存在A\[z\]，A\[x\] < A\[z\] < a\[y\]，则与选择A\[y\]相比，将会得到更长的上升子序列。

再根据条件(3)，我们会得到一个启示：根据F\[\]的值进行分类。对于F\[\]的每一个取值k，我们只需要保留满足F\[i\] = k的所有A\[i\]中的最小值。设D\[k\]记录这个值，即D\[k\] = min\{A\[i\]\} (F\[i\] = k)。

注意到D\[\]的两个特点：

(1) D\[k\]的值是在整个计算过程中是单调不上升的。  
(2) D\[\]的值是有序的，即D\[1\] < D\[2\] < D\[3\] < ... < D\[n\]。

利用D\[\]，我们可以得到另外一种计算最长上升子序列长度的方法。设当前已经求出的最长上升子序列长度为len。先判断A\[i\]与D\[len\]。若A\[i\] > D\[len\]，则将A\[i\]接在D\[len\]后将得到一个更长的上升子序列，len = len + 1， D\[len\] = A\[i\]；否则，在D\[1\]..D\[len\]中，找到最大的j，满足D\[j\] < A\[i\]。令k = j + 1，则有D\[j\] < A\[i\] <= D\[k\]，将A\[i\]接在D\[j\]后将得到一个更长的上升子序列，同时更新D\[k\] = A\[i\]。最后，len即为所要求的最长上升子序列的长度。

在上述算法中，若使用朴素的顺序查找在D\[1\]..D\[len\]查找，由于共有O(n)个元素需要计算，每次计算时的复杂度是O(n)，则整个算法的时间复杂度为O(n^2)，与原来的算法相比没有任何进步。但是由于D\[\]的特点(2)，我们在D\[\]中查找时，可以使用二分查找高效地完成，则整个算法的时间复杂度下降为O(nlogn)，有了非常显著的提高。需要注意的是，D\[\]在算法结束后记录的并不是一个符合题意的最长上升子序列！

这个算法还可以扩展到整个最长子序列系列问题，整个算法的难点在于二分查找的设计，需要非常小心注意。