(linear DP | monotone queue) acwing 895 Longest ascending subsequence

895. Longest ascending subsequence

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

Method 1 ：dp

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

using namespace std;
int a[1010],c[1010];
int main(){
    
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int res=0;
    for(int i=1;i<=n;i++){
    
        for(int j=1;j<i;j++){
    
            if(a[j]<a[i])
                c[i]=max(c[i],c[j]);
        }
        c[i]+=1;
        res=max(res,c[i]);
    }
    cout<<res;
    return 0;
}

Method 2 ： A monotonous queue

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

using namespace std;

int a[1010],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;
    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;
}