O(nlogn)的算法關(guān)鍵是它建立了一個(gè)數(shù)組temp[]，temp[i]表示長(zhǎng)度為i的不下降序列中結(jié)尾元素的最小值，用top表示數(shù)組目前的長(zhǎng)度，算法完成后top的值即為最長(zhǎng)不下降子序列的長(zhǎng)度。
設(shè)當(dāng)前的以求出的長(zhǎng)度為top，則判斷num[i]和temp[top]：
1.如果num[i]>=temp[top]，即num[i]大于長(zhǎng)度為top的序列中的最后一個(gè)元素，這樣就可以使序列的長(zhǎng)度增加1，即top++,然后現(xiàn)在的temp[top]=num[i]； 2.如果num[i]< temp[top]，那么就在temp[1]…temp[top]中找到最大的j,使得temp[j]< num[i],然后因?yàn)閠emp[j]< num[i]，所以num[i]大于長(zhǎng)度為j的序列的最后一個(gè)元素，那么就可以更新長(zhǎng)度為j+1的序列的最后一個(gè)元素，即temp[j+1]=num[i]。
總結(jié)一個(gè)例子： 1 2 8 4 3 5 的原序列中，我們通過這個(gè)算法得到的序列是 1 2 3 5，而不能是1 2 4 5.因?yàn)槊看斡洃浀氖情L(zhǎng)度為i的末尾數(shù)字最小的序列，因此1 2 3 優(yōu)于1 2 4,選擇1 2 3,將5接在后面。
5 1 2 2 4 3 out:1 2 3
//做一個(gè)序列，維護(hù)這個(gè)序列 //最長(zhǎng)上升子序列 #include<cstdio>#include<iostream>using namespace std;int n,top,a[1001],d[1001];//d[i]表示長(zhǎng)度為i的有序序列中末尾最小的數(shù) 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++) 二.最長(zhǎng)不降子序列：5 1 2 2 4 3 out: 1 2 2 3
//做一個(gè)序列，維護(hù)這個(gè)序列 //最長(zhǎng)不降子序列 #include<cstdio>#include<iostream>using namespace std;int n,top,a[1001],d[1001];//d[i]表示長(zhǎng)度為i的有序序列中末尾最小的數(shù) 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: “元素值>查找值”的第一個(gè)元素的位置 lower_bound: “元素值>=查找值”的第一個(gè)元素的位置
//最長(zhǎng)不下降子序列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個(gè)元素特判一下 { 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 //否則就找一個(gè)最該替換的替換掉 { int j=upper_bound(d+1,d+len+1,a[i])-d; //找到第一個(gè)大于它的d的下標(biāo) d[j]=a[i]; } } printf("%d/n",len); return 0;}最長(zhǎng)上升子序列：
//最長(zhǎng)不下降子序列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個(gè)元素特判一下 { 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 //否則就找一個(gè)最該替換的替換掉 { int j=lower_bound(d+1,d+len+1,a[i])-d; //找到第一個(gè)>=它的d的下標(biāo) if(d[j]==a[i] || d[j-1]==a[i]) continue; d[j]=a[i]; } } printf("%d/n",len); return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
