贪心+二分
using namespace std;
#define ll long long
const int N=100005;
int dp[N];
int low[N];
int a[N],n,V,ans;
int serch(int anss,int a)
{
int l=1,r=anss,mid;
while(l<r)
{
mid=l+r>>1;
if(low[mid]<a)
{
l=mid+1;
}else
{
r=mid;
}
}
return l; //尽可能往左找 返回l
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
low[i]=9999999;
}
low[1]=a[1];
ans=1;
for(int i=2;i<=n;i++)
{
if(a[i]>low[ans])
{
low[++ans]=a[i];//如果a[i]大于low末尾元素就添上a[i] 更新长度ans和low[]
}else
{
// 二分找到low数组中第一个大于等于a[i]的元素 更新low[j]
low[serch(ans,a[i])]=a[i];
}
}
cout<<ans;
return 0;
}