题解 | 最长不下降子序列

维护一个最优的上升数组，如果当前的a[i]大于等于最优的上升数组的最后一个就把这个加到后面，否则找到第一个严格大于a[i]的位置，将其替换成a[i]，哎哎哎，好久以前学的有些忘了都

void solve(){
    int n;
    cin>>n;
    vector<int> b;
    int a[n+1];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int ans=1;
    for(int i=1;i<=n;i++){
        if(b.empty())b.push_back(a[i]);
        else{
            if(a[i]<b.back()){
                int L=0,R=b.size()-1,pos=0;
                while(L<=R){
                    int mid=(L+R)>>1;
                    if(b[mid]>a[i]){
                        pos=mid;
                        R=mid-1;
                    }else{
                        L=mid+1;
                    }
                }
                ans=max(ans,pos+1);
                b[pos]=a[i];
            }else{
                b.push_back(a[i]);
                ans=max(ans,(int)b.size());
            }
        }
    }cout<<ans<<'\n';
}