Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1023991
  • 博文数量: 242
  • 博客积分: 10209
  • 博客等级: 上将
  • 技术积分: 3028
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-12 09:27
文章分类

全部博文(242)

文章存档

2014年(1)

2013年(1)

2010年(51)

2009年(65)

2008年(124)

我的朋友

分类: C/C++

2010-04-09 14:10:25

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

L=<a1,a2,…,an>n个不同的实数的序列,L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>,其中k12<…maK1k2<…km。求最大的m值。


第一种算法:转化 为LCS问题求解

设序列X=<b1,b2,…,bn>是对序列L=<a1,a2,…,an>按递增排好序的序列。那么显然X与L的最长公共子序列即为L的最长递增子序列。这 样就把求最长递增子序列的问题转化为求最长公共子序列问题LCS了。


最长公共子序列问题用动态规划的算法可 解。设Li=< a1,a2,…,ai>,Xj=< b1,b2,…,bj>,它们分别为L和X的子序列。令C[i,j]为Li与Xj的最长公共子序列的长度。则有如下的递推方程:

这可以用时间复杂度为O(n2)的算法求解。求最长递增子序列的算法时间复杂度由排序所用的O(nlogn)的 时间加上求LCS的O(n2) 的时间,算法的最坏时间复杂度为O(nlogn)+O(n2)=O(n2)。


第二种算法:动态规划法


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

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

这个递推方程的意思是,在 求以ai为末元素的最长递增子序列时,找到所有序号在 i 前面且小于ai的元素aj,即jaji。如果这样的元素存在,那么对所有aj,都有一个以aj为 末元素的最长递增子序列的长度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

阅读(1115) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~