2176985_ac_0ms_72k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
int n,a[1<<20],x,max;

int s(int m,int p,int q)
{
	int t;
	while(p<=q)
	{
		t=(p+q)/2;
		if(a[t]<=m) p=t+1;
		else
		{
			if(t-1<0||a[t-1]<=m) return t;
			else q=t-1;
		}
	}
	return -1;
}
int main()
{
	scanf("%d",&n);
	for(int i = 0; i < n; i++)
		scanf("%d",&a[i]);
	max=0;
	for(i=1;i<n;i++)
	{
		if(a[i]<a[0]) a[0]=a[i];
		else if(a[i]>a[max]) {max++; a[max]=a[i];}
		else 
		{
			x=s(a[i],0,max);
			a[x]=a[i];
		}
	}
	max++;
	printf("%d\n",max);
	return 1;
}