dp

int main(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<i;++j){
            if(a[i]>a[j])f[i]=max(f[i],f[j]+1);
        }
    }
    for(int i=1;i<=n;++i)ans=max(f[i],ans);
    return 0;
}

贪心

int main(){
    for(int i=1;i<=n;++i){
        if(a[i]>d[len])d[++len]=a[i];
        else {
            int j=lower_bound(d+1,d+1+len,a[i])-d;
            d[j]=a[i];
        }
    }
    return 0;
}

树状数组：

struct BIT{
    int c[N];
    int lowbit(int x){return x&(-x);}
    void modify(int i,int val){
        while(i<=n){
            c[i]=max(c[i],val);
            i+=lowbit(i);
        }
    }
    int query(int i){
        int res=0;
        while(i>0){
            res=max(res,c[i]);
            i-=lowbit(i);
        }
        return res;
    }
}S;
struct node{
    int id,w;
}a[N];
bool cmp(node a,node b){
    if(a.w!=b.w)return a.w<b.w;
    return a.id<b.id;
}
int main(){
    n=read();
    for(int i=1;i<=n;++i)a[i].w=read(),a[i].id=i;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;++i){
        int maxn=S.query(a[i].id);
        maxn++;
        S.modify(a[i].id,maxn);
        ans=max(ans,maxn);
    }
    printf("%d\n",ans);
    return 0;
}

关于树状数组，其实学了cdq分治之后就显然了，额···其实就是优化dp