操作后得到的序列的最长不降子序列是前面一串 $1$ 后面接着一串 $2$。翻转前它就是一串 $1$、一串 $2$、一串 $1$、一串 $2$。因此枚举中间的 $2$ 和 $1$ 的分界点 $i$,其中 $i$ 被包含于 $[l,r]$,求出 $1\sim l$ 中 $1$ 的数量加 $l+1\sim i$ 中 $2$ 的数量加 $i+1\sim r$ 的 $1$ 的数量加 $r+1 \sim n$ 的 $2$ 的数量最大值。时间复杂度 $O(n^2)$。
简单 DP 一下可以优化到 $O(n)$。代码:
#include<bits/stdc++.h>
#define int long long
#define py puts("YES")
#define pn puts("NO")
#define pf puts("-1")
#define hh puts("")
#define db puts("!!!!!!")
#define pb(x) push_back(x)
#define ci const int
#define fstr(STRING) for(int i=0;i<(int)STRING.size();++i)
#define fn() for(int i=1;i<=n;++i)
#define fo(OOO) for(int OOO=1;OOO<=n;++OOO)
#define ina int n,a[N];
#define rna n=re();fn()a[i]=re();
using namespace std;
inline int re(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch&15),ch=getchar();return x*f;}
void work();
signed main(){int g=1;//cin>>g;
while(g--)work();}
const int N = 1e6 + 5;
ina;
bool a2(){
fn()if(a[i]==1)return 0;return 1;
}
bool a1(){
fn()if(a[i]==2)return 0;return 1;
}
int dp[2][N];
int s1[N],s2[N];
void work(){
rna;if(a2()||a1()) {
cout<<n;return;
}
fn()s1[i]=s1[i-1]+(a[i]==1);fn()s2[i]=s2[i-1]+(a[i]==2);
for (int i = 1; i <= n; ++i) {
dp[0][i] = max(dp[0][i - 1] + (a[i] == 2), s1[i - 1] + (a[i] == 2));
}int res = 0;
for(int i = n; i >=1;--i) {
dp[1][i] = max(dp[1][i + 1] + (a[i + 1]==1), s2[n] - s2[i]);res =max(res, dp[0][i]+dp[1][i]);
}cout << res;
}