这里我先给出 $O(N^3)$ 的算法，它已经足够解决本题。然后，对于感兴趣的读者，我会展示如何实现 $O(N)$ 的解法。

$O(N^3)$ 方法

首先要注意的是，数据范围足够小，允许使用暴力枚举算法。我们可以计算每一种可能的单次操作后得到的 $1$ 的数量，然后取最大值。

具体做法：用两个 FOR 循环枚举所有区间 $[i, j]$（$i \le j$），这一步复杂度为 $O(N^2)$。对于每个固定的 $i$ 和 $j$，我们需要计算执行翻转操作后 $1$ 的个数 cnt。

为此，我们再遍历一遍数组 $a[]$（$O(N)$ 时间），总复杂度为 $O(N^3)$。对于每个下标 $k$，分两种情况：

• 如果 $k$ 在区间 $[i, j]$ 内（即 $i \le k \le j$），则该位置被翻转，因此向 cnt 中添加 $1 - a[k]$（注意：$0$ 变 $1$，$1$ 变 $0$）。
• 如果 $k$ 不在区间内，则直接向 cnt 中添加 $a[k]$。

最终答案为所有 cnt 中的最大值。

$O(N)$ 方法

为了达到线性复杂度，我们需要做一个观察。假设我们翻转某个区间（可以是任意区间），并设 $S$ 为翻转前数组中 $1$ 的数量。那么翻转会发生什么？

• 每翻转一个 $0$，$S$ 增加 $1$（获得一个新的 $1$）。
• 每翻转一个 $1$，$S$ 减少 $1$（失去一个 $1$）。

我们定义翻转的“收益”：当遇到 $0$ 时收益为 $+1$，当遇到 $1$ 时收益为 $-1$。由此我们可以构建一个新的数组 $b[]$：

• 若 $a[i] = 0$，则 $b[i] = 1$
• 若 $a[i] = 1$，则 $b[i] = -1$

翻转后的 $1$ 的数量为 $S + \text{gain}$，其中 $\text{gain}$ 是区间 $[i, j]$ 内 $b$ 数组的和。由于 $S$ 是常数，我们只需要最大化 $\text{gain}$。

换句话说，我们只需要在 $b$ 数组中找到和最大的子数组（子序列要求连续）。翻转这个子数组对应的区间，就能得到最多的 $1$。

找到最大和子数组可以用 Kadane 算法 在 $O(N)$ 时间内完成。如果你还不熟悉这个经典问题，建议先学习它，再回来看这个解法。

#include <iostream>
using namespace std;
int n,a,b=-1,s,q;
main()
{
	cin>>n;
	while(n--) 
	{
		cin>>a;
		s+=a;
		q+=1-2*a;
		b=max(b,q);
		q=max(0,q);
	}
	cout<<s+b;
}