最长非减字串2 (二分查找) 银牌

//最长递增（非减少）子序列

//给定长度尾部最小值递推动态规划，O(nlogn)

#include<bits/stdc++.h>

using namespace std;

int main(){

    int n;

    cin>>n;

    vector<int> a;

    for(int i=0;i<n;i++){

        int x;

        cin>>x;

        auto ip=upper_bound(a.begin(),a.end(),x);

        if(ip==a.end()){//larger than anything ending

            a.push_back(x);

        }else{

            if(*ip>x){

            *ip=x;//replace larger minimal value

            }

        }

    }

    cout<<a.size()<<endl;

}