最长不降子序列lis

《最长不降子序列lis》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、LIS。。LongestIncreasingSubsequence；最长上升/不下降子序列；　　最长上升子序列：　　有两种基本方法：两个时间复杂度分别为O(n^2)和O(nlogn)　　先来看第1种：　　动态规划：　　对于给定数列E，元素个数为n,最长上升子序列Q满足对任意1<=i

2、　　代码如下：　　#include　　usingnamespacestd;　　intn;　　inta[1001],b[1001];　　intmain()　　{inti,j;　　scanf("%d",&n);　　for(i=1;i<=n;i++)　　{　　scanf("%d",&a[i]);　　b[i]=1;　　}　　for(i=1;i<=n;i++)　　{intmaxx=0;　　for(j=1;j<=i;j++)　　{ 　　if(a[i]>a[j]&&b[j]>maxx)　　{maxx=b[j];　　}　　}　　b[i]=

3、maxx+1;　　}　　intbest=0;　　for(i=1;i<=n;i++)　　{if(bests，则置为栈顶；如果a

4、[i]表示所有长度为i的上升子序列中最小的最后一个数.　　•　　举例：原序列为3，4，5，2，4，2　　栈为3，4，5，此时读到2，则用2替换3，得到栈中元素为2，4，5，再读4，用4替换5，得到2，4，4，再读2，得到最终栈为2，2，4,最终得到的解是: 　　长度为1的上升子序列中最小的最后一个数是2(2)　　长度为2的上升子序列中最小的最后一个数是2(2,2)长度为3的上升子序列中最小的最后一个数是4(3,4,4) 　　可知没有长度为4的上升子序列,最长递增子序列长度为3.(3,4,4)　　CMI本质是LIS问题的另一种动态规划思路　　注

5、意:CMI只能求LIS的长度和最后一个数,不能求LIS的序列!　　代码如下：　　#include　　usingnamespacestd;　　intn;　　inta[1001],b[1001];　　intrear;　　intsolve(intt)　　{intl=1,r=rear;　　while(l<=r)　　{intmid=(l+r)>>1;　　if(b[mid]>=t)//若为非递减序列，则为b[mid]>t　　r=mid-1;　　else 　　l=mid+1;　　}　　if(l>rear)　　rear=l;　　retur

6、nl;　　}　　intmain()　　{inti,j;　　scanf("%d",&n);　　rear=0;　　for(i=1;i<=n;i++)　　{　　scanf("%d",&a[i]);　　b[solve(a[i])]=a[i];　　}　　printf("%d",rear);　　system("pause");　　return0;　　}