最长上升子序列，最长不下降子序列

深藏阁楼爱情的钟 2022-05-13 22:55 342阅读 0赞

最长上升子序列

#include<iostream>
    #include<cstdio>
    using namespace std;
    const int N=23333+12;
    int dp[N],a[N];
    int n;
    
    int binarysearch(int k,int len){
        int l=1;
        int r=len;
        int mid=(l+r)>>1;
        while(l<=r){
            if(k==dp[mid]){
                return mid;
            }
            else if(k>dp[mid]){
                l=mid+1;
            }
            else{
                r=mid-1;
            }
            mid=(l+r)>>1;
    
        }
        return l;
    }
    int main(){
        int len;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
    
        }
        dp[1]=a[0];
        len=1;
        for(int i=1;i<n;i++){
            int t=binarysearch(a[i],len);
            dp[t]=a[i];
            if(t>len){
                len=t;
            }
    
        }
        printf("%d\n",len);
    }

最长不下降子序列

#include<iostream>
    #include<cstdio>
    using namespace std;
    const int N=23333+10;
    int dp[N],a[N];
    
    int binarysearch(int k,int len){
        int l=0,r=len-1;
        while(l<=r) {
            int mid=(l+r)>>1;
            if(k<dp[mid]) {
                r=mid-1;
            } else {
                l=mid+1;
            }
        }
        return l;
    }
    int main() {
        int n,len;
        scanf("%d",&n);
    
        for(int i=0; i<n; i++) {
            scanf("%d",&a[i]);
        }
        len=0;
        for(int i=0;i<n;i++){
            int t=binarysearch(a[i],len);
            if(t>=len) len++;
            dp[t]=a[i];
        }
         printf("%d\n",len);
    }

其实只要把这个条件改一下，就可以变成最长上升子序列，但是我习惯了第一种写法，所以写出两种记录一下，第一种写法本来就改一下条件就行了的，可能是二分没写好，有些极端情况，导致有的题目只过了98的数据