$ (\overbrace{111111}^{\text{第一部分}}) (\overbrace{22222}^{\text{第二部分}})(\overbrace{111111}^{\text{第三部分}}) (\overbrace{22222}^{\text{第四部分}}) $
注:第一、二、三、四均可能为空。(因为翻转后第三段可能长)所以取s3,s4的max
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
int s1 = 0, s2 = 0, s3 = 0, s4 = 0; //4段
while (n -- )
{
int x;
scanf("%d", &x);
if (x == 1) { s1 ++, s3 = max(s3 + 1, s2 + 1);}
if (x == 2) { s2 = max(s1 + 1, s2 + 1), s4 = max(s3 + 1, s4 + 1);}
}
printf("%d\n", max(s3, s4));
return 0;
}
DP抄自抽风神(tql)和ming神
记 $f[i][j]$ 表示只考虑 $a_1∼a_i$的好子序列,且好子序列的最后一个数在第 $j$ 部分的子序列集合。
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1000005;
int n, x, res;
int f[N][4];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &x);
f[i][1] = f[i - 1][1] + (x == 1);
f[i][2] = max(f[i - 1][1], f[i - 1][2]) + (x == 2);
f[i][3] = max(f[i - 1][2], f[i - 1][3]) + (x == 1);
f[i][4] = max(f[i - 1][3], f[i - 1][4]) + (x == 2);
}
for (int i = 1; i <= 4; ++i) res = max(res, f[n][i]);
printf("%d\n", res);
return 0;
}