动态规划

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
long long arr[100005];
long long dp[100005];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&arr[i]);
	dp[1]=arr[1];
	int cnt=1;
	for(int i=2;i<=n;i++)
	{
		if(arr[i]>=dp[cnt])dp[++cnt]=arr[i];
		else
		{
			int x=upper_bound(dp+1,dp+1+cnt,arr[i])-dp;
			dp[x]=arr[i];
		}
	} 
	cout<<cnt<<endl;
}