C++14(g++5.4) 解法, 执行用时: 691ms, 内存消耗: 652K, 提交时间: 2020-10-09 22:05:01

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin>>n;
	vector<int> a(n+1,0),b(n+1,0);
	int t=0;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		for(int j=i-1; j>=0; j--) 
			if(a[i]>=a[j]) 
				b[i]=max(b[j]+1,b[i]);
		t=max(b[i],t);
	}
	cout<<t<<endl;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 17ms, 内存消耗: 888K, 提交时间: 2018-08-29 20:25:07

#include<bits/stdc++.h>
int a,n,ans,k,g[100005];
int main(){
    std::cin>>n; memset(g,0x3f,sizeof g);
    for(int i=1;i<=n;i++) std::cin>>a,g[k=std::upper_bound(g+1,g+1+n,a)-g]=a,ans=std::max(ans,k);
    std::cout<<ans;return 0;
}

pypy3 解法, 执行用时: 1406ms, 内存消耗: 24968K, 提交时间: 2023-03-31 12:36:49

n = int(input())
nlist = []
for _ in range(n):
    a = int(input())
    nlist.append(a)
dp = [1]*n
for i in range(n):
    for k in range(i):
        if nlist[i] >= nlist[k]:
            dp[i] = max(dp[i],dp[k]+1)
print(max(dp))