codeforces Flipping Game 题解

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 n integers: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.

sample test(s)

本题因为数据量小，可以使用暴力法，时间效率是o(n^3)

但是这里巧用最大子段和的思想，可以把时间效率降到o(n)

思想：

1 想使用一个新的数列，计算连续出现了多少个1和连续出现了多少个零

2 求这个新数列的最大子段和

3 flip最大子段中的 0 和 1,

4 计算出结果

比暴力法复杂很多了，但是时间效率却提高了三个档次。