最长不降子序列优化

2/22/2017来源:ASP.NET技巧人气:798

O(nlogn)的算法关键是它建立了一个数组temp[],temp[i]表示长度为i的不下降序列中结尾元素的最小值,用top表示数组目前的长度,算法完成后top的值即为最长不下降子序列的长度。

设当前的以求出的长度为top,则判断num[i]和temp[top]:

1.如果num[i]>=temp[top],即num[i]大于长度为top的序列中的最后一个元素,这样就可以使序列的长度增加1,即top++,然后现在的temp[top]=num[i]; 2.如果num[i]< temp[top],那么就在temp[1]…temp[top]中找到最大的j,使得temp[j]< num[i],然后因为temp[j]< num[i],所以num[i]大于长度为j的序列的最后一个元素,那么就可以更新长度为j+1的序列的最后一个元素,即temp[j+1]=num[i]。

总结一个例子: 1 2 8 4 3 5 的原序列中,我们通过这个算法得到的序列是 1 2 3 5,而不能是1 2 4 5.因为每次记忆的是长度为i的末尾数字最小的序列,因此1 2 3 优于1 2 4,选择1 2 3,将5接在后面。

一.最长上升子序列:

5 1 2 2 4 3 out:1 2 3

//做一个序列,维护这个序列 //最长上升子序列 #include<cstdio> #include<iostream> using namespace std; int n,top,a[1001],d[1001];//d[i]表示长度为i的有序序列中末尾最小的数 int binary(int l,int r,int x) { if(l<=r) { int mid=(l+r)/2; if(x==d[mid]) return mid;//找见==的,替换 else if(x<d[mid]) binary(l,mid,x); else { if(x<d[mid+1]) return mid+1; else binary(mid+1,r,x); } } } int main() { scanf("%d",&n); scanf("%d",&a[1]); top=1,d[top]=a[1]; for(int i=2;i<=n;i++) { scanf("%d",&a[i]); if(a[i]>d[top]) d[++top]=a[i]; else{ if(a[i]<d[1]) d[1]=a[i]; else d[binary(1,top,a[i])]=a[i];// } } cout<<top<<endl; //for(int i=1;i<=top;i++) PRintf("%d ",d[i]);不是结果子序列的值 }

二.最长不降子序列:

5 1 2 2 4 3 out: 1 2 2 3

//做一个序列,维护这个序列 //最长不降子序列 #include<cstdio> #include<iostream> using namespace std; int n,top,a[1001],d[1001];//d[i]表示长度为i的有序序列中末尾最小的数 int binary(int l,int r,int x) { if(l<=r) { int mid=(l+r)/2; if(x<d[mid]) binary(l,mid,x); else {//x>= x=2:2 2 4 找见4, x=3:2 2 4找见4 if((x>d[mid] || x==d[mid]) && x<d[mid+1]) return mid+1; else binary(mid+1,r,x); } } } int main() { scanf("%d",&n); scanf("%d",&a[1]); top=1,d[top]=a[1]; for(int i=2;i<=n;i++) { scanf("%d",&a[i]); if(a[i]>=d[top]) d[++top]=a[i]; else{ if(a[i]<d[1]) d[1]=a[i]; else d[binary(1,top,a[i])]=a[i];// } } cout<<top<<endl; }

这是另一种写法,用stl里面的upper_bound() upper_bound: “元素值>查找值”的第一个元素的位置 lower_bound: “元素值>=查找值”的第一个元素的位置

//最长不下降子序列nlogn Song #include<cstdio> #include<algorithm> using namespace std; int a[40005]; int d[40005]; int main() { int n; scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); if (n==0) //0个元素特判一下 { printf("0\n"); return 0; } d[1]=a[1]; //初始化 int len=1; for (int i=2;i<=n;i++) { if (a[i]>=d[len]) d[++len]=a[i]; //如果可以接在len后面就接上 else //否则就找一个最该替换的替换掉 { int j=upper_bound(d+1,d+len+1,a[i])-d; //找到第一个大于它的d的下标 d[j]=a[i]; } } printf("%d\n",len); return 0; }

最长上升子序列:

//最长不下降子序列nlogn Song #include<cstdio> #include<algorithm> #include<iostream> using namespace std; int a[40005]; int d[40005]; int main() { int n; scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); if (n==0) //0个元素特判一下 { printf("0\n"); return 0; } d[1]=a[1]; //初始化 int len=1; for (int i=2;i<=n;i++) { if (a[i]>d[len]) d[++len]=a[i]; //如果可以接在len后面就接上 else //否则就找一个最该替换的替换掉 { int j=lower_bound(d+1,d+len+1,a[i])-d; //找到第一个>=它的d的下标 if(d[j]==a[i] || d[j-1]==a[i]) continue; d[j]=a[i]; } } printf("%d\n",len); return 0; }