贪心+二分

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;
}