#include<bits/stdc++.h>
using namespace std;
int f[1000001],a[1000001],l,k;
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;
		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;
    return 0;
}

将原来的dp数组的存储由数值换成该序列中，上升子序列长度为i的上升子序列，的最小末尾数值

这其实就是一种几近贪心的思想：我们当前的上升子序列长度如果已经确定，那么如果这种长度的子序列的结尾元素越小，后面的元素就可以更方便地加入到这条我们臆测的、可作为结果、的上升子序列中。