最长单调递增子序列

╰+哭是因爲堅強的太久メ 2022-05-24 01:49 249阅读 0赞

单调子序列包含有单调递增子序列和递减子序列，不失一般性，这里只讨论单调递增子序列。首先，从定义上明确我们的问题。给定序列a1, a2, …, an，如果存在满足下列条件的子序列

ai1<=ai2<=…<=aim, (其中i1<i2<…<im)

即称为一个原序列的长度为m的单调递增子序列，那么，现在的问题是我们要找出一个序列的最长的单调递增子序列。

直观上来说，一个序列Sn，它有2n个子序列，枚举所有的子序列，找出其中单调递增的序列，然后返回其中最长的，这样我们的问题就解决了。当然，这个直观的算法在时间上为O(2n\*n)，它的复杂度增长太快了，所以，我们还应该做得更好一些。

于是，我们换个角度思考。假设我们对Sn排序（递增），得到Sn’。那么，Sn和Sn’的最长公共子序列Cm就是我们要求的最长单调递增子序列（如果你不清楚最长公共子序列的定义，just google it）。为什么？假设Cm’是Sn的最长单调子列，且Cm’!=Cm， Cm’的长度大于Cm。由于Cm’是递增的，并且Cm’的每一个元素都来自Sn，所以Cm’一定是Sn’的子列，而Cm’又是Sn的子列，所以Cm’是Sn和Sn’的公共子列，故Cm’的长度一定小于Cm，这与假设矛盾，所以Cm是最长单调子列。理论上我们的算法是正确的，复杂度方面，运用动态规划(dynamic programming)来求解LCS（最长公共子列，Longest-Common-Subsequence），时间上是O(n2)，空间上也是O(n2)。于是，对Sn排序需要nlogn的时间，而LCS需要n2，最后，我们的算法时间上是O(n2)。

可以看到，通过上面的改进，我们的算法效率得到了很大的提升（从指数增长到多项式增长）。不过，程序设计的乐趣就是它会不断地给我们一些惊喜，所以，就此打住不是我们该做的，于是，更好的算法应该是存在的。

对于序列Sn，考虑其长度为i的单调子列(1<=i<=m)，这样的子列可能有多个。我们选取这些子列的结尾元素（子列的最后一个元素）的最小值。用Li表示。易知

L1<=L2<=…<=Lm

如果Li>Lj(i<j)，那么去掉以Lj结尾的递增子序列的最后j-i个元素，得到一个长度为i的子序列，该序列的结尾元素ak<=Lj<Li，这与Li标识了长度为i的递增子序列的最小结尾元素相矛盾，于是证明了上述结论。现在，我们来寻找Sn对应的L序列，如果我们找到的最大的Li是Lm，那么m就是最大单调子列的长度。下面的方法可以用来维护L。

从左至右扫描Sn，对于每一个ai，它可能

(1)    ai<L1，那么L1=ai

(2)    ai>=Lm，那么Lm+1=ai，m=m+1 (其中m是当前见到的最大的L下标)

(3)    Ls<=ai<Ls+1，那么Ls+1=ai

扫描完成后，我们也就得到了最长递增子序列的长度。从上述方法可知，对于每一个元素，我们需要对L进行查找操作，由于L有序，所以这个操作为logn，于是总的复杂度为O(nlogn)。优于开始O(n2)的算法。这里给出我的一个实现：（算法并没有返回具体的序列，只是返回长度）

#include <fstream>
    #include <iostream>
    using namespace std;
    
    void OutputArray( int * data, int len){
    	for( int i=0; i<len; i++){
    		cout << data[i] <<" ";
    	}
    	cout << endl;
    }
    
    template<typename T>
    int BSearch(const T* S, int size, const T e )
    {
    	int low = 0;
    	int high = size-1;
    	while( low <= high )
    	{
    		int mid = (low+high)/2;
    		if( S[mid] <= e)
    			low = mid+1;
    		else{
    			if( low == high ) break;
    			high = mid;
    		}
    	}
    
    	if( low == size )
    		return -1;
    	else
    		return low;
    
    }
    
    template <typename T>
    int LMS (const T * data, int size, T* &S)
    {
    	if (size <= 0)
        return 0;
      
        S = new T[size];
        int S_Count = 1;
        S[0] = data[0];
     
        for (int i = 1; i < size; i++)
        {
             const T & e = data[i];
             int index = BSearch( S, S_Count, e);
    
    		 if( index==-1 ) //说明e>Sm
     			S[S_Count++] = e;
             else if ( (index==S_Count-1)&&(S[S_Count-1]==e) ){ //e=Sm
                S[S_Count++] = e;
    		 }
             else			//其他情况
                 S[index] = e;
         }
     
         return S_Count;
     }
    
    int main()
    {
    	int data[12] = {0,1,0,3,4,2,5,3,8,2,4,5};
    	//int data[3] ={5,8,4};
    	//HeapSort(data, 9);
    	OutputArray(data, 12);
    	cout <<endl;
    	int *res;
    	int count = LMS(data,12, res);
    	cout <<count<<endl;
    	OutputArray(res, count);
        return 0;
    }

另：最长单调子序列及其计数问题

http://hi.baidu.com/vincentz/blog/item/6df5a3c2be3ffa180ef477e2.html