最长非递减子序列--顺丰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("%dn",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;
}

最后

以上就是靓丽小懒虫为你收集整理的最长非递减子序列--顺丰2020校招笔试题的全部内容，希望文章能够帮你解决最长非递减子序列--顺丰2020校招笔试题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。