用树状数组的版本
原理网上都有
复杂度:$O(nlogn)$

#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
int n,c[maxn],a[maxn],b[maxn];
inline int lowbit(int& x)
{
    return x&(-x);
}
inline void modify(int pos,int val)
{
    for(int i=pos;i<=n;i+=lowbit(i))
        c[i]=max(c[i],val);
}
inline int query(int pos)
{
    int ans=0;
    for(int i=pos;i;i-=lowbit(i))
        ans=max(ans,c[i]);
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
    int k=unique(b+1,b+n+1)-b-1,ans=0,tp;
    for(int i=1;i<=n;++i)
        a[i]=lower_bound(b+1,b+k+1,a[i])-b;//离散化
    for(int i=1;i<=n;++i)
    {
        tp=query(a[i]-1);//注意要减一
        modify(a[i],++tp);
        ans=max(ans,tp);
    }
    printf("%d\n",ans);
    return 0;
}