模板题 nlog(n)
;const int MAXN = 1000000 + 5;int g[MAXN],len,n,a[MAXN];int find(int x){int l = 0,r = n;int mid = (l + r) / 2;while(l <= r){if(g[mid] < x)l = mid + 1;else if(g[mid] > x)r = mid – 1;elsereturn mid;mid = (l + r) / 2;}return l;}void dpdpd(){len = 1;memset(g,0x3f,sizeof(g));g[0] = -1;g[1] = a[1];for(int i = 2;i <= n;i ++){int j = find(a[i]);g[j] = min(g[j],a[i]);len = max(len,j);}return;}int main(){scanf(“%d”,&n);for(int i = 1;i <= n;i ++)scanf(“%d”,&a[i]);dpdpd();printf(“%d\n”,len);return 0;}
，漫无目的的生活就像出海航行而没有指南针
