P1049-题解（C++代码,这不是我写的，我写的更麻烦，你们可以参考一下）

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<algorithm> 
using namespace std;
int a[1001],n;
int b[1001]={0},k=0;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	 cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		if(a[i]>b[k-1])
		{//如果a[i]大于b数组中的最后一个数 b[k]=a[i]且b数组长度+1 
			b[k++]=a[i];
		}
		else
		{
		  int r=upper_bound(b,b+k,a[i])-b;//二分查找在b中第一个大于a[i]的位置 
		  b[r]=a[i];
		}
	}
	cout<<k<<endl;
	return 0;
}