(greedy + longest ascending subsequence) acwing 896 Longest ascending subsequence II

896. Longest ascending subsequence II

Topic link https://www.acwing.com/problem/content/898/
subject ：

Ideas ： Find less than in the queue t The subscript of the largest number of .a[0] Initialize minimum , Make sure that the number you enter must be in... At the time of two minutes a[0] To the right of

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;

int a[100010],k;
int erfen(int u){
    
    int l=0,r=k;
    while(l<r){
    
        int mid=l+r+1>>1;
        if(a[mid]<u) l=mid;
        else r=mid-1;
    }
    return l;
}
int main(){
    
    int n;
    cin>>n;
    a[0]=-1e9-10;
    for(int i=0;i<n;i++){
    
        int t;
        scanf("%d",&t);
        int index=erfen(t);
        a[++index]=t;
        k=max(k,index);
    }
    cout<<k;
    return 0;
}