转载 最长递增字串LIS问题

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

设L=<a₁,a₂,…,a_n>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<a_K1,a_k2,…,a_km>，其中k₁2<…m且a_K1k2<…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为末元素的最长递增子序列的长度。则有如下的递推方程：

f(i) = max { f(j), j

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

伪代码如下：

// n 为串a[ ]的长度

//引入数组b是为了在最后输出最长递增子串；

//以a[t]为末元素的最长递增子串 是由 以a[b[t]]为末元素的最长递增子串 + a[t] 组成。


int *b = (int *) malloc(n*sizeof(int)); 


memset(b, 0, n*sizeof(n));





for(int i=0; i < n; i++){

    f[i] = 1;

    int temp = 0;


    for(int j=0; j < i; j++){

        if(a[j] < a[i] && temp < f[j])

            temp = f[j];

            b[i] = j;

    }

    f[i] = temp + 1;


}//整个大的for循环结束以后，f[i] (i=0....n-1) 中存放的就是以ai为末元素的最长递增字串长度。

//此时要得到最长递增字串长度，只需扫描一次f[ ]数组找出最大值即可。

int max = 0;

int *c = (int *)malloc(n*sizeof(int));  //数组c用来存放最长递增子串


for(i=0,temp=0; i

    if(max < f[i]){

        max = f[i];

        temp = i;


    }

do{


    c[i++] = a[temp];

    temp = b[temp];

}while(temp != 0);

for(i=i-1; i>=0; i--)

    printf("%d\t",c[i]);





上述算法的复杂度为O(n^2)。

第三种算法：改进了的动态规划法
    第二种算法中标为红色的部分，是一个查找最大值的过程，其复杂度为O(n)，如果我们将所有的f[j]值
有序存放，然后使用二分查找，使红色部分的复杂度达到O(log n)，那么整个算法的复杂度就为O(n log n)。
这个我现在有点搞不通了，明天再继续吧
参考：
http://dev.csdn.net/develop/article/60/60443.shtm
http://hi.baidu.com/smilngsky/blog/item/99e3cdeebf234c3aacafd5e2.html
http://blog.csdn.net/hhygcy/archive/2009/03/02/3950158.aspx