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 計算出結果

比暴力法複雜很多了，但是時間效率卻提高了三個檔次。