#include<iostream> #include<cstdio> using namespace std; const int N=1000; int num[N]; int bs(int r,int key) { int l=0; while(l<=r) { int mid=(l+r)/2; if(num[mid]<key) l=mid+1; else r=mid-1; } return l; } int lcs(int n) { int top=0; int k; for(int i=1;i<n;++i) { k=bs(top,num[i]); if(k>top) top=k; num[k]=num[i];//维护数组num的前一段,贪心保存当前最长子序列,对于下一个未放进去的元素,若大于nun[top],则放进num[top+1], } //相应top要+1,否则,替换top前第一个大于该元素的值 return top+1; } int main() { int i,n; scanf("%d",&n); for(i=0;i<n;++i) scanf("%d",&num[i]); printf("%d\n",lcs(n)); return 0; }