Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1840801
  • 博文数量: 160
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 5794
  • 用 户 组: 普通用户
  • 注册时间: 2013-01-23 18:56
个人简介

将晦涩难懂的技术讲的通俗易懂

文章分类

全部博文(160)

文章存档

2019年(14)

2018年(19)

2017年(9)

2016年(26)

2015年(18)

2014年(54)

2013年(20)

分类: C/C++

2014-04-18 00:35:18

问题描述:

求一个正整数序列的最长单调自增子序列,子序列不要求是连续的。例如

Input5

5 2 4 3 1

Output2

(1) 算法复杂度是O(N*N)

f[i]是以a[i]为最大值的子序列,那么f[]的最大值就是要的结果。


点击(此处)折叠或打开

  1. int f[],a[];
  2. f[0] = 1;
  3. for(i = 1 ; i < n ; i++ )
  4. {
  5.   f[i] = 1;
  6.   for(j = 0 ; j < i ; j++)
  7.   {
  8.     If(a[j] < a[i] && f[j]+1 > f[i])//等号有没有要视题目而定
  9.     {
  10.       f[i] = f[j] +1;
  11.     }
  12.   }
  13. }


很显然实践复杂度是O(N*N),那么有没有更快的算法呢?按照正常的思路更快的复杂度应该就是O(N*logN),那么就要涉及到二分了。

(2)算法复杂度是O(N*logN)

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

L1<=L2<=…<=Lm

    因为:如果Li>Lj(i,那么去掉以Lj结尾的递增子序列的最后j-i个元素,得到一个长度为i的子序列,该序列的结尾元素ak<=Lj,这与Li标识了长度为i的递增子序列的最小结尾元素相矛盾,于是证明了上述结论。(注:之前要使L保存这些序列的最小值就是为了使此公式成立,即L有序。只有L有序我们才能方便的利用二分查找法创建L)。

     现在,我们来寻找Sn对应的L序列,如果我们找到的最大的LiLm,那么m就是最大单调子列的长度。下面的方法可以用来创建和维护L

   

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

(1)    ai,那么L1=ai

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

(3)    ai<Lm,则找到s,使得Ls<=ai,那么Ls+1=ai

   

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


点击(此处)折叠或打开

  1. int find(int *a,int len,int n)//二分find
  2. {
  3.   int left=0,right=len,mid=(left+right)/2;
  4.   while(left<=right)
  5.   {
  6.     if(n>a[mid]) left=mid+1;
  7.     else if(n<a[mid]) right=mid-1;
  8.     else return mid;
  9.     mid=(left+right)/2;
  10.   }
  11.   return left;//注:这里查找不到时要返回left,因为结束时left指向较大值。
  12. }


  1.     L[0]=-1;//要懂得用这种天然的最小值
  2.     L[1]=a[0];//初始化
  3.    for(i=1;i<n;i++)//复杂度是N的
  4.     {
  5.       j=find(L,n+1,a[i]);//找到第三步中的s+1
  6.       L[j]=a[i];
  7.     }
  8.     


阅读(2664) | 评论(0) | 转发(1) |
0

上一篇:同余定理

下一篇:C的“类型提升”

给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册