3367. 咸鱼翻身

单点时限: 2.0 sec

内存限制: 256 MB

海边躺着一排咸鱼，一些有梦想的咸鱼成功翻身（然而没有什么卵用），一些则是继续当咸鱼。大佬 kblack 想要帮这些咸鱼翻身，但是他比较懒，所以只会从某只咸鱼开始，往一个方向，一只只咸鱼翻过去，翻转若干只后就转身离去，深藏功与名，但是很不幸，kblack 的一通操作，也很可能让一些原本拥有梦想的咸鱼失去梦想。

更准确地说，kblack 会选择一个区间 [L,R]，改变区间内所有咸鱼原本的状态。注意至少翻转一条咸鱼。

kblack 离开后想知道如果他采取最优策略，最多有多少条咸鱼成功翻身。

输入格式

一个整数 n (1≤n≤105)。

接下来一行 n 个整数，0 表示没有翻身，1 表示处于翻身状态，数据保证只有 0 和 1。

输出格式

在大佬 kblack 的操作后，最多有多少咸鱼拥有梦想（即 1 的最大数量）。

样例

input

6

0 0 0 1 1 1

output

6

input

6

0 1 1 0 0 0

output

5

/*
思路：翻0的贡献是1，翻1的贡献是-1，这样转化为最大连续子区间和，这是翻了后的最大和，最终结果还要加上原先1的个数，因为在最大区间中若存在1翻回去，贡献是-1，实际上不应该减1，而应该0，意思是对当前1的总个数没有影响，如果真将翻1贡献设为0，就必须统计出最大连续子区间中1的个数，最终结果变成加上除了此区间剩余1的个数了，这样不如设置-1，方便统计。所以无论如何要加上原先1的总个数，无需考虑此区间存不存在1。
*/
#include<iostream>
using namespace std;
int flag[100001];
int main() {
	int n;
	cin>>n;
	int count=0;
	for(int i  =0; i < n; i++) {
		cin>>flag[i];
		if(flag[i]) {
			flag[i]=-1;
			count++;
		} else
			flag[i]=1;
	}
	int sum1=0,sum2=0;
	for(int i = 0; i < n; i++) {
		sum1+=flag[i];
		if(sum2<sum1)
			sum2=sum1;
		if(sum1<0)
			sum1=0;
	}
	if(count==n)
	cout<<n-1<<endl;
	else
	cout<<sum2+count;
	return 0;
}