最长上升子序列（nlogn算法）

#include<iostream> using namespace std; const int maxn=1000000; int n,j,a[maxn],c[maxn],len; int find(int l,int r,int x) { if(l==r) return l; int mid=(l+r)>>1; if(c[mid]<x) return find(mid+1,len,x); else return find(l,mid,x); } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; len=1;c[1]=a[1]; for(int i=1;i<=n;i++) { if(a[i]>c[len]) j=++len; else j=find(1,len,a[i]); c[j]=a[i]; } cout<<len; return 0; } #include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int maxn=100010; int n,tot,a[maxn],f[maxn],c[maxn]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { if(a[i]>c[tot]) { c[++tot]=a[i]; f[i]=tot; } else { int pos=upper_bound(c+1,c+tot+1,a[i])-c; c[pos]=a[i];f[i]=pos; } } printf("%d",tot); return 0; }