最长非递减子序列--顺丰2020校招笔试题

n的范围是[0,100000]

DP版本（O(n^2))时间复杂度(LTE）：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100
int main()
{
    int A[N],dp[N],n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>A[i];
    }
    for(int i=0;i<n;i++)
    {
        dp[i]=1;
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(A[j]<=A[i])
            dp[i]=max(dp[i],dp[j]+1);
        }
        
    }
    int m=dp[0];
    for(int i=0;i<n;i++)
    {
        m=max(m,dp[i]);
    }
    cout<<m;

    return 0;
}

O(n)复杂度

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

using namespace std;

const int N = 1000000;
const int INF = 1e9;
int a[N],dp[N],n;

void solve(){
    fill(dp,dp + n,INF);
    for(int i = 0;i < n;i ++){
        *upper_bound(dp,dp + n,a[i]) = a[i];
    }
    printf("%d\n",lower_bound(dp,dp + n,INF) - dp);
}

int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i ++){
        scanf("%d",&a[i]);
    }
    solve();
    return 0;
}