#include<bits/stdc++.h>
using namespace std;
int a[100001];
int f[100001];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		f[i]=0x7fffffff;
		//初始值要设为INF
		/*原因很简单，每遇到一个新的元素时，就跟已经记录的f数组当前所记录的最长
		上升子序列的末尾元素相比较：如果小于此元素，那么就不断向前找，直到找到
		一个刚好比它大的元素，替换；反之如果大于，么填到末尾元素的下一个q，INF
                就是为了方便向后替换啊！*/ 
	}
	f[1]=a[1];
	int len=1;//通过记录f数组的有效位数，求得个数 
	/*因为上文中所提到我们有可能要不断向前寻找，
	所以可以采用二分查找的策略，这便是将时间复杂
    度降成nlogn级别的关键因素。*/ 
	for(int i=2;i<=n;i++)
	{
		int l=0,r=len,mid=0;
		if(a[i]>f[len]) f[++len]=a[i];
		//如果刚好大于末尾，暂时向后顺次填充 
		else 
		{
			while(l<r)
			{	
		 	   mid=(l+r)/2;
		 	   if(f[mid]>a[i])r=mid;
				//如果仍然小于之前所记录的最小末尾，那么不断
				//向前寻找(因为是最长上升子序列，所以f数组必
				//然满足单调) 
				else l=mid+1; 
			}
		f[l]=min(a[i],f[l]);//更新最小末尾 
     	}
    }
    cout<<len<<endl;
	return 0;
}

再分享一个nlogn做法 这种做法打印序列会比较麻烦，因为它没有记录每一条子序列的数值，而是只记录了末尾的数值 但在处理数据规模更大的题时可以 （这个是过不去这道的）

#include<bits/stdc++.h>
using namespace std;
int b[2000][4],n,l,k,i,j;//b[i][1]是这个数本身，b[i][2]是从i位置到n的最长不下降序列长度，b[i][3]是从i位置的最长不下降序列的下一个数 
int main()
{
	int x,h=1;
	while(cin>>x)
	{
		b[h++][1]=x;
		b[h][2]=1;b[h][3]=0;
	}
	for(i=h-1;i>=1;i--)
	{
		l=0;k=0;//l暂时是当前不下降的长度，这一轮循环完了才会被存储到b[i][2] 
		for(j=i+1;j<=h;j++)
		{
			if((b[j][1]>=b[i][1])&&(b[j][2]>l))
			{
				l=b[j][2];
				k=j;//保存后继元素便于之后的输出~ 
			}
			if(l>0)//这个是为了防0的 
			{
				b[i][2]=l+1;//如果取当前这个数，长度就+1 
				b[i][3]=k;
			}
		}
		
	} 
	k=1;
	for(j=1;j<=h;j++)
	{
		if(b[j][2]>b[k][2]) k=j;//求最长不下降序列的起始位置 
	}
	cout<<"max="<<b[k][2]<<endl;
	while(k!=0)
	{
		cout<<b[k][1]<<' ';
		k=b[k][3];
	}
	return 0;
}