3549. 最长非递减子序列

给定一个长度为 n 的数字序列 a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​，序列中只包含数字 1 和 2。

现在，你要选取一个区间 [l,r](1≤l≤r≤n)[l,r](1≤l≤r≤n)[l,r](1≤l≤r≤n)，将 al,al+1,…,ara_l,a_{l+1},…,a_ral​,al+1​,…,ar​进行翻转，并且使得到的新数字序列 a 的最长非递减子序列的长度尽可能长。

请问，这个最大可能长度是多少？

一个非递减子序列是指一个索引为 p1,p2,…,pkp_1,p_2,…,p_kp1​,p2​,…,pk​ 的序列，满足 p1

输入格式

第一行一个整数 n。

第二行 n 个空格隔开的数字 1 或 2，表示 a1,…,ana_1,…,a_na1​,…,an​。

输出格式

输出一个整数，表示得到的新数字序列 a 的最长非递减子序列的最大可能长度。

数据范围

对于 30% 的数据，1≤n≤1001≤n≤1001≤n≤100。
对于 100% 的数据，1≤n≤1061≤n≤10^61≤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

分析：

按照题意，我们翻转一个区间 [l,r][ l , r ][l,r]之后，将会得到最大的非递减上升子序列。那么其翻转之前的形式应该是如下的：

所以可能有四种合法情况：

• 只有第一段存在，111111…，用 s1 记录第一种情况的长度
• 第一段和第二段都存在，111111122222…，用 s2 记录第二种情况的长度
• 前三段都存在，11111222211111，用 s3 记录第三种情况的长度
• 四段全部存在，11111222211112222，用 s4 记录第四种情况的长度
• 最后的答案即为 max{ s1,s2,s3,s4 }
• 时间复杂度:O(n)O(n)O(n)

代码：

#include
using namespace std;int main(){int n ;cin>>n;int s1 = 0,s2 = 0,s3 = 0,s4 = 0;for(int i = 1;i <= n;i++){int x;scanf("%d",&x);//如果x = 1，有可能是加在 s1 后面，也有可能是加在 s3 后面//s1   111111....//s3   11111222211111...if(x == 1){s1++;//s3 此时的情况有可能是   1111122222 + 1 //也有可能是  1111122221111...  + 1//所以要取两者的最大值s3 = max(s3+1,s2+1);}//x = 2既有可能是加在 s2 后面，也有可能是加在 s4 后面//s2 111112222....//s4 11111222211112222....else{s2 = max(s1+1,s2+1);s4 = max(s3+1,s4+1);}}cout<