给出一个 1 ～ n (n ≤ 10^5) 的排列 P
求其最长上升子序列长度
第一行一个正整数n，表示序列中整数个数；
第二行是空格隔开的n个整数组成的序列。
最长上升子序列的长度
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<algorithm> #include<cstring> const int MAXN=100010; using namespace std; struct tree{ int l,r,ma; }a[4*MAXN]; int dp[MAXN],n,ans=0,nn=0; int lian[MAXN]; void cl(){ memset(dp,0,sizeof(dp)); memset(lian,0,sizeof(lian)); } void build(int id,int l,int r){ if(l==r){ a[id].l=l; a[id].r=r; a[id].ma=0; return; } a[id].l=l; a[id].r=r; int mid=(l+r)/2; build(id*2,l,mid); build(id*2+1,mid+1,r); a[id].ma=max(a[id*2].ma,a[id*2+1].ma); } int kanxun(int id,int l,int r){ int L=a[id].l,R=a[id].r,mid=(L+R)/2; if(l==L&&r==R){ return a[id].ma; } if(r<=mid) return kanxun(id*2,l,r); if(l>mid) return kanxun(id*2+1,l,r); else return max(kanxun(id*2,l,mid),kanxun(id*2+1,mid+1,r)); } void insert(int id,int aum,int x){ int l=a[id].l,r=a[id].r,mid=(l+r)/2; if(l==r&&l==aum){ a[id].ma=x; return; } if(aum<=mid) insert(id*2,aum,x); else insert(id*2+1,aum,x); a[id].ma=max(a[id*2].ma,a[id*2+1].ma); } int main(){ cl(); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&lian[i]),nn=max(nn,lian[i]); dp[0]=0; build(1,1,nn); for(int i=1;i<=n;i++){ int j; if(lian[i]==1) j=0; else j=kanxun(1,1,lian[i]-1); dp[i]=j+1; insert(1,lian[i],dp[i]); } for(int i=1;i<=n;i++) ans=max(ans,dp[i]); printf("%d",ans); }
鬼畜版：
#include<iostream> #include<algorithm> #include<stdio.h> #include<stdlib.h> #include<cstring> using namespace std; int dp[1000010]; int main(){ memset(dp,0,sizeof(dp)); int n,maxi=0,l,r,mid,ans=0; scanf("%d",&n); for(int i=1;i<=n;i++){ int x; scanf("%d",&x); l=1,r=maxi,ans=0; while(l<=r){ mid=(l+r)/2; if(x>=dp[mid]) ans=mid,l=mid+1; else r=mid-1; } if(ans==maxi) dp[++maxi]=x; else dp[ans+1]=min(dp[ans+1],x); } printf("%d",maxi); return 0; }
原文：http://www.cnblogs.com/renjianshige/p/7192409.html