Codeforces Round #191 (Div. 2) A. Flipping Game【*枚举/DP/每次操作可将区间[i,j](1=<i<=j<=n)内牌的状态翻转（即0变1,1变0），求一次翻转操作后，1的个数尽量多】

Iahub got bored, so he invented a game to be played on paper.

He writes n integers a1, a2, ..., an. Each of those integers can be either 0 or 1. He's allowed to do exactly one move: he chooses two indices i and j (1 ≤ i ≤ j ≤ n) and flips all values ak for which their positions are in range [i, j] (that is i ≤ k ≤ j). Flip the value of x means to apply operation x = 1 - x.

The goal of the game is that after exactly one move to obtain the maximum number of ones. Write a program to solve the little game of Iahub.

Input

The first line of the input contains an integer n (1 ≤ n ≤ 100). In the second line of the input there are nintegers: a1, a2, ..., an. It is guaranteed that each of those n values is either 0 or 1.

Output

Print an integer — the maximal number of 1s that can be obtained after exactly one move.

Examples

input

5
1 0 0 1 0

output

input

4
1 0 0 1

output

Note

In the first case, flip the segment from 2 to 5 (i = 2, j = 5). That flip changes the sequence, it becomes: [1 1 1 0 1]. So, it contains four ones. There is no way to make the whole sequence equal to [1 1 1 1 1].

In the second case, flipping only the second and the third element (i = 2, j = 3) will turn all numbers into 1.

【题意】：题意是输入一个只有0和1的序列，要求找出一个合理的区间，在这个区间里面把0变成1，1变成0，使得该区间和该区间外的1的个数达到最大。

【分析】：暴力，遍历每个区间段，小区间内的1个数 = 小区间长度 - 小区间内1的个数。小区间外1个数 = 大区间1个数 - 小区间内1个数。然后每次更新。

dp，就是求出最大区间0的个数（这个区间中1的影响为-1，0的影响为1），然后加上所有1个数就是最终答案了。

【代码】：

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

const int maxn = 100+10;

int main()
{
    int n, a[maxn], i, j, k, count1, count0, max, t0, t1, t;
    while (cin >> n)
    {
        for (t = i = 0; i < n; i++)
        {
            scanf("%d", &a[i]); 
            if (a[i])
                t++;  // 统计整个序列中1的个数

        }
        max = -1;
        for (i = 0; i < n; i++)
        {   
            for (j = i; j < n; j++)
            {
                count1 = count0 = 0;
                for (k = i; k <= j; k++) // 暴搜，统计每个区间的0、1数目
                {
                    if (a[k]==1)          
                        count1++;
                    else
                        count0++;
                }
                if (max < count0 - count1) //max保存的是当前0、1数目最大的差（0最多，1最少）
                {
                    max = count0 - count1;
                }
            }
        }
        printf("%d
", t + max);
    }               
    return 0;
}

暴力枚举

#include <iostream>  
#include <string>  
#include <algorithm>  
using namespace std;  
  
int main()  
{  
    int n, x, mx = 0;  
    cin >> n;  
    int cnt0 = 0, cnt1 = 0;  
    for (int i = 0; i < n; ++i)  
    {  
        cin >> x;  
        if (x == 1) ++cnt1; //整个区间中1的个数  
        if (x == 0)  
        {  
            ++cnt0;  
            if (cnt0 > mx)  //翻转区间所得最多1的个数  
                mx = cnt0;  
        }  
        else if (cnt0) --cnt0; //1的值对cnt0的取值影响为-1  
    }  
    if (mx == 0) --mx; //没有0，那么至少也要翻一次  
    cout << mx + cnt1 << '
';  
    return 0;  
}