题目描述
给定一个长度为 $n$ 的数字序列 $a_1,a_2,…,a_n$,序列中只包含数字 1 和 2。
现在,你要选取一个区间 $[l,r]$$(1≤l≤r≤n)$,将 $a_l,a_{l+1},\ldots,a_r$ 进行翻转,并且使得到的新数字序列 $a$ 的最长非递减子序列的长度尽可能长。
请问,这个最大可能长度是多少?
一个非递减子序列是指一个索引为 $p_1,p_2,…,p_k$ 的序列,满足 $p_1<p_2<…<p_k$ 并且 $a_{p_1}≤a_{p_2}≤…≤a_{p_k}$,其长度为 $k$。
输入格式
第一行一个整数 $n$。
第二行 $n$ 个空格隔开的数字 1 或 2,表示 $a_1,…,a_n$。
输出格式
输出一个整数,表示得到的新数字序列 $a$ 的最长非递减子序列的最大可能长度。
数据范围
对于 30% 的数据,$1≤n≤100$。
对于 100% 的数据,$1≤n≤10^6$。
本题读入数据规模较大,需注意优化读入。
C++ 尽量使用 scanf
读入,Java 尽量使用 BufferedReader
读入。
输入样例
10
1 1 2 2 2 1 1 2 2 1
输出样例
9
算法
$O(n)$
最需要仔细想的是,在翻转的时候,子序列如何影响了结果。
对于子序列,一个思考的小技巧,应该就是先想想子串的情况是什么,因为其实子序列就是子串里面塞进“噪音”,即不相关的东西。比如本题的设定里,考虑“112122”的最长非递减子序列的话,第一个2就是“噪音”,“11122”就是要研究的子串对象。
所以就很容易想到,最”舒服“的情况就是有比如“112221112222”,当中的“222111”就是要翻转的地方,而不是其他的,所以只需要看能够形成类似的子序列就行。
具体思考下去,那么可能形成的最长的子序列的样子应该形如”1111“,”11112222“,”111222211“或者“111122221122”这四种。前两个不需要翻转,即 $l=r$;后两个就是需要翻转的情况。如何统计的方式可以看代码,四个形式分别对应s1
,s2
,s3
,s4
。
C++ 代码
#include <cstdio>
#include <cmath>
using namespace std;
int s1, s2, s3, s4;
int main() {
int n, m;
scanf("%d", &n);
while (n--) {
scanf("%d", &m);
if (m == 1) {
s1++;
s3 = max(s2 + 1, s3 + 1);
}
else {
s2 = max(s1 + 1, s2 + 1);
s4 = max(s3 + 1, s4 + 1);
}
}
printf("%d", max(s3, s4));
return 0;
}