方法 O(NlogN)

细节

• 体会一下，minEnd[0]初始化为无穷小的目的

具体逻辑见注释

#include<iostream>
#include<cstring>
using namespace std;

#define ffor(i,s,e) for(int i=s;i<e;++i)
#define read(x) scanf("%d", &x);

const int N = 100008;
const int INF=1e9;

int gn;
int a[N],minEnd[N];


int bs(int l,int r,int goal){
    if(l>r) return -1;//本题不会出现
    while(l<r){
        int mid=(l+r+1)>>1;
        if(minEnd[mid]<goal) l=mid;//查找目标值可以接的前驱
        else r=mid-1;
    }
    return l;
}
int main()
{
    cin>>gn;
    ffor(i,0,gn) read(a[i]);

    memset(minEnd,0x7f,sizeof minEnd);
    minEnd[0]=-INF;

    int Len=1;//上升子序列的长度
    ffor(i,0,gn){
        int pre=bs(0,Len,a[i]);//查找目标值可以接的前驱
        minEnd[pre+1]=min(a[i],minEnd[pre+1]);//添加之前先检查
        Len= pre==Len ? pre+1:Len;//到末尾了，要更新总长度
    }

    cout<<Len<<endl;
    return 0;
}