搞一个序列d，不断维护这个序列
以【0，8，4，12，2】为例
第一趟d={0,0}
第二趟d={0,0,8}
第三趟d={0,0,4}
第四趟d={0,0,4,12}
第五趟d={0,0,2,12}
输出的答案是3

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    while(cin>>n){
        int len=1;
        vector<int> d(n+1,0),v(n);
        for(int i=0;i<n;i++) cin>>v[i];
        d[len]=v[0];
        for(int i=0;i<n;i++){
            if(v[i]>d[len]) d[++len]=v[i];
            else{
                int l=1,r=len,mid,pos=0;
                while(l<r){
                    mid=(l+r)>>1;
                    if(d[mid]<v[i]){
                        pos=mid;
                        l=mid+1;
                    }
                    else r=mid;
                }
                d[pos+1]=v[i];
            }
        }
        cout<<len<<endl;
    }
    return 0;
}

有不懂的地方欢迎随时提问（想点赞的就点赞）