记录编号	309762	评测结果	AAAAAAAAAA
题目名称	1398.最长上升子序列	最终得分	100
用户昵称	zjh001	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2016-09-20 16:08:04	内存使用	9.39 MiB

//最长上升子序列 nlog(n) 模板 
#include <stdio.h>
#define MAXN 1000005
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b

int n;
int a[MAXN];
int f[MAXN];
int hash[MAXN],r;
int ans;

int search(int x)
{
	int left,right;
	left=1,right=r;
	
	while (left <right)
	{
		int mid=left+(right-left)/2;
		if (hash[mid] >= x) right=mid;
		else left=mid+1; 
	}
	
	return left;
}

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]);
	
	hash[1]=a[1],f[1]=1;
	r=2;
		
	for (int i=2;i<=n;i++)
	{
		int down=search(a[i]);
		
		if (down==r) hash[down]=a[i],r++;
		else hash[down]=min(hash[down],a[i]);
		
		f[i]=down;
	}
	
	for (int i=1;i<=n;i++)
		ans=max(f[i],ans);
	
	printf ("%d\n",ans);
	
	return 0;
}