题目描述
给定一个长度为 n 的数字序列 a1,a2,…,an,序列中只包含数字 1 和 2。
现在,你要选取一个区间 l,r,将 al,al+1,…,ar 进行翻转,并且使得到的新数字序列 a 的最长非递减子序列的长度尽可能长。
请问,这个最大可能长度是多少?
一个非递减子序列是指一个索引为 p1,p2,…,pk 的序列,满足 p1<p2<…<pk 并且 ap1≤ap2≤…≤apk,其长度为 k。
输入格式
第一行一个整数 n。
第二行 n 个空格隔开的数字 1 或 2,表示 a1,…,an。
输出格式
输出一个整数,表示得到的新数字序列 a 的最长非递减子序列的最大可能长度。
数据范围
对于 30% 的数据,1≤n≤100。
对于 100% 的数据,1≤n≤106。
本题读入数据规模较大,需注意优化读入。
C++ 尽量使用 scanf 读入,Java 尽量使用 BufferedReader 读入。
样例
输入样例1:
4
1 2 1 2
输出样例1:
4
输入样例2:
10
1 1 2 2 2 1 1 2 2 1
输出样例2:
9
算法1
(dp) $O(n)$
时间复杂度
参考文献
python3 代码
n = int(input())
nums = [int(x) for x in input().split()]
s1 = 0
s12 = 0
s121 = 0
s1212 = 0
for x in nums:
if x == 1:
s1 += 1
s121 = max(s12 + 1, s121 + 1)
else:
s12 = max(s1 + 1, s12 + 1)
s1212 = max(s121 + 1, s1212 + 1)
res = max(s121, s1212)
print(res)
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
int s1 = 0;
int s12 = 0;
int s121 = 0;
int s1212 = 0;
int x;
while (n --)
{
scanf("%d", &x);
if (x == 1)
{
s1 += 1;
s121 = max(s12 + 1, s121 + 1);
}
else
{
s12 = max(s1 + 1, s12 + 1);
s1212 = max(s121 + 1, s1212 + 1);
}
}
int res = max(s121, s1212);
cout << res << endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla