求最长上升子序列的nlgn做法,用数组d[i]记录长度为i的上升子序列最后一个数为多少,每次直接比较~
用到了二分~
#include<cstdio>
#define ll long longll n,a[1000001],d[1000001],len;ll findd(ll u)
{ll l=1,r=len;while(l<r){ll mid=(l+r)>>1;if(d[mid]>=u && d[mid-1]<u) return mid;else if(d[mid]<u) l=mid+1;else r=mid-1;}return l;
}int main()
{scanf("%lld",&n);for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);d[++len]=a[1];for(ll i=2;i<=n;i++){ll j;if(a[i]>d[len]) j=++len;else if(a[i]<d[1]) j=1;else j=findd(a[i]);d[j]=a[i];}printf("%lld\n",len);return 0;
}