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;
}