EOJ 3367. 鹹魚翻身

3367. 鹹魚翻身

DESCRIPTION SUBMIT STATISTICS DISCUSSION

Time limit per test: 2.0 seconds

Memory limit: 256 megabytes

海邊躺着一排鹹魚，一些有夢想的鹹魚成功翻身（然而沒有什麼卵用），一些則是繼續當鹹魚。大佬 kblack 想要幫這些鹹魚翻身，但是他比較懶，是以隻會從某隻鹹魚開始，往一個方向，一隻隻鹹魚翻過去，翻轉若幹隻後就轉身離去，深藏功與名，但是很不幸，kblack 的一通操作，也很可能讓一些原本擁有夢想的鹹魚失去夢想。

更準确地說，kblack 會選擇一個區間  [L,R] ，改變區間内所有鹹魚原本的狀态。注意至少翻轉一條鹹魚。

kblack 離開後想知道如果他采取最優政策，最多有多少條鹹魚成功翻身。

Input

一個整數  n   (1≤n≤105) 。

接下來一行  n  個整數， 0  表示沒有翻身， 1  表示處于翻身狀态，資料保證隻有  0  和  1 。

Output

在大佬 kblack 的操作後，最多有多少鹹魚擁有夢想（即  1  的最大數量）。

Examples

input

6
0 0 0 1 1 1
      

output

6
      

input

6
0 1 1 0 0 0
      

output

5
      

Source

2017.9.27 ACM 選拔賽

#include<bits/stdc++.h>
const int N = 1e5+10;
int a[N];
using namespace std;
int main()
{
    int n;
    cin>>n;
    int cnt=0;
    for(int i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
        if(a[i])cnt++;
    }
    if(cnt==n)
        cout<<n-1<<endl;
    else
    {
        int maxhere=0,maxnum=0;
        for(int i=0;i<n;i++)
        {
            if(a[i])
                maxhere--;
            else maxhere++;
            if(maxhere<0)maxhere=0;
            maxnum=max(maxhere,maxnum);
        }
        cout<<maxnum+cnt<<endl;

    }
    return 0;
}