记录编号	205032	评测结果	AAAAAAAAAA
题目名称	最长上升子序列	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2015-11-04 19:46:54	内存使用	0.30 MiB

#include<cstdio>
using namespace std;
int n,len,a[1005],c[1005],l,r;
int main(){
    freopen("lis1.in","r",stdin);
    freopen("lis1.out","w",stdout);
   scanf("%d",&n);
   for(int i=1;i<=n;++i) scanf("%d",&a[i]);
   len=1;c[len]=a[1];
   for(int i=2;i<=n;++i){
		if(a[i]>c[len]) c[++len]=a[i];
		else{
			l=1,r=len;
			while(l<=r){
				int mid=(l+r)>>1;
				if(c[mid]<a[i]) l=mid+1;
				else r=mid-1;
			}
			c[l]=a[i];
		}
   }
   printf("%d",len);
}