C++(g++ 7.5.0) 解法, 执行用时: 79ms, 内存消耗: 16196K, 提交时间: 2022-09-16 17:28:17

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2e4,M=50;
ll s[maxn+5],dp[maxn+5],pre[55][maxn+5],las[55][maxn+5];
int main(){
	ll n,i,j,k,slsl,wz,ans=0;
	scanf("%lld",&n);
	for(i=1;i<=n;i++) scanf("%lld",&s[i]);
	for(i=1;i<=M;i++){
		slsl=0;
		for(j=1;j<=n;j++){
			if(s[j]>=i){
				if(slsl==0 or s[j]>=dp[slsl]) dp[++slsl]=s[j];
				else{
					wz=upper_bound(dp+1,dp+1+slsl,s[j])-dp;
					dp[wz]=s[j];
				}
			}
			pre[i][j]=slsl;
		}
	}
	for(i=1;i<=M;i++){
		slsl=0;
		for(j=n;j>=1;j--){
			if(s[j]<=i){
				if(slsl==0 or M+1-s[j]>=dp[slsl]) dp[++slsl]=M+1-s[j];
				else{
					wz=upper_bound(dp+1,dp+1+slsl,M+1-s[j])-dp;
					dp[wz]=M+1-s[j];
				}
			}
			las[i][j]=slsl;
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=M;j++){
			ans=max(ans,las[j][n+2-i]+pre[j][n+1-i]);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

C++ 解法, 执行用时: 56ms, 内存消耗: 9616K, 提交时间: 2022-06-04 13:17:00

#include<bits/stdc++.h>
#define ll long long
#define eb emplace_back
using namespace std;
const int M=2e4+9;
int n,ans;
int a[M];
int dp[M],p[M][59],s[M][59];
void sol(int v){
	int l=0;
	for(int i=1;i<=n;++i){
		if(a[i]>=v){
			int x=upper_bound(dp+1,dp+l+1,a[i])-dp;
			dp[x]=a[i];
			l=max(l,x);
		}
		p[i][v]=l;
	}
	l=0;
	for(int i=n;i>=1;--i){
		if(a[i]<=v){
			int x=upper_bound(dp+1,dp+l+1,-a[i])-dp;
			dp[x]=-a[i];
			l=max(l,x);
		}
		s[i][v]=l;
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i];
	for(int i=1;i<=50;++i){
		sol(i);
		for(int j=1;j<=n;++j){
			ans=max(ans,p[j-1][i]+s[j][i]);
		}
	}
	cout<<ans<<endl;
	return 0;
}
/*
8
5 5 3 3 2 2 1 1 
*/