最长递增子序列

最长递增子序列问题的求解

 

最长递增子序列问题是一个很基本、较常见的小问题，但这个问题的求解方法却并不那么显而易见，需要较深入的思考和较好的算法素养才能得出良好的算法。由于这个问题能运用学过的基本的算法分析和设计的方法与思想，能够锻炼设计较复杂算法的思维，我对这个问题进行了较深入的分析思考，得出了几种复杂度不同算法，并给出了分析和证明。

一，    最长递增子序列问题的描述

设L=<a₁,a₂,…,a_n>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<a_K1,a_k2,…,a_km>，其中k₁<k₂<…<k_m且a_K1<a_k2<…<a_km。求最大的m值。

二，    第一种算法：转化为LCS问题求解

设序列X=<b₁,b₂,…,b_n>是对序列L=<a₁,a₂,…,a_n>按递增排好序的序列。那么显然X与L的最长公共子序列即为L的最长递增子序列。这样就把求最长递增子序列的问题转化为求最长公共子序列问题LCS了。

最长公共子序列问题用动态规划的算法可解。设Li=< a₁,a₂,…,a_i>,Xj=< b₁,b₂,…,b_j>，它们分别为L和X的子序列。令C[i,j]为Li与Xj的最长公共子序列的长度。则有如下的递推方程：

这可以用时间复杂度为O(n²)的算法求解，由于这个算法上课时讲过，所以具体代码在此略去。求最长递增子序列的算法时间复杂度由排序所用的O(nlogn)的时间加上求LCS的O(n²)的时间，算法的最坏时间复杂度为O(nlogn)＋O(n²)＝O(n²)。

三，    第二种算法：动态规划法

设f(i)表示L中以a_i为末元素的最长递增子序列的长度。则有如下的递推方程：

这个递推方程的意思是，在求以a_i为末元素的最长递增子序列时，找到所有序号在L前面且小于a_i的元素a_j，即j<i且a_j<a_i。如果这样的元素存在，那么对所有a_j,都有一个以a_j为末元素的最长递增子序列的长度f(j)，把其中最大的f(j)选出来，那么f(i)就等于最大的f(j)加上1，即以a_i为末元素的最长递增子序列，等于以使f(j)最大的那个a_j为末元素的递增子序列最末再加上a_i；如果这样的元素不存在，那么a_i自身构成一个长度为1的以a_i为末元素的递增子序列。

四，    对第二种算法的改进

在第二种算法中，在计算每一个f(i)时，都要找出最大的f(j)(j<i)来，由于f(j)没有顺序，只能顺序查找满足a_j<a_i最大的f(j)，如果能将让f(j)有序，就可以使用二分查找，这样算法的时间复杂度就可能降到O(nlogn)。于是想到用一个数组B来存储“子序列的”最大递增子序列的最末元素，即有

B[f(j)] = a_j

在计算f(i)时，在数组B中用二分查找法找到满足j<i且B[f(j)]=a_j<a_i的最大的j,并将B[f[j]+1]置为a_i。

 

代码如下：

 

 

 

#include <iostream>

#define  LEN  6
using namespace std;

void show(int a[],int N)
{
    for(int i=0; i<N; i++) cout<<a[i]<<"  ";
    cout<<endl;
}

void findMaxLen(int a[],int f[],int n,int len)
{
    int i,max=0;

    if(n>0)
    {
        for(i=n-1;i>=0;i--)
        {
            if(a[i]<=a[n]&&f[i]>=max) max =f[i];
        }
    }
    else{
        f[n] = 1;
    }

    if(max!=0){
        f[n] = max + 1;
    }
    else f[n]=1;
}

int main()
{

    int a[LEN]={1,3,4,2,7,5};
    int f[LEN]={0};
    int max =0;

/*  没有改进的O(n2)
    for(int i=0;i<LEN;i++)
    {
        findMaxLen(a,f,i,5);
        if(f[i]>=f[max])max =i;
    }

    cout<<a[max]<<endl;

    show(f,LEN);
    
    */

//改进后的O(nlogn)
    int b[LEN]={0};
    b[0] = -10000;
    b[1] = a[0];
    int maxLen=1;

    for(int i=1;i<LEN;i++)
    {
        int mid,left=0,right=maxLen;
        while(left<=right)
        {
            mid = (left+right)/2;
            if(b[mid]<a[i])left = mid+1;
            else right = mid-1;
        }
        b[left] = a[i];
        if(left > maxLen) maxLen++;
    }

    cout<<maxLen<<endl;
    show(b,LEN);

}

 

评论

1 楼 liuzhiqiangruc 2012-06-03  

我感觉是不是不用这么麻烦？http://liuzhiqiangruc.iteye.com/blog/1549458
这是我写的实现，欢迎讨论。