327A.md (1583B)
1 Source: https://codeforces.com/problemset/problem/327/A 2 3 A. Flipping Game 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Iahub got bored, so he invented a game to be played on paper. 22 23 He writes *n* integers *a*1, *a*2, ..., *a**n*. 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 *a**k* 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*. 24 25 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. 26 27 Input 28 29 The first line of the input contains an integer *n* (1 ≤ *n* ≤ 100). In the second line of the input there are *n* integers: *a*1, *a*2, ..., *a**n*. It is guaranteed that each of those *n* values is either 0 or 1. 30 31 Output 32 33 Print an integer — the maximal number of 1s that can be obtained after exactly one move. 34 35 Examples 36 37 Input 38 39 ``` 40 5 41 1 0 0 1 0 42 ``` 43 44 Output 45 46 ``` 47 4 48 ``` 49 50 Input 51 52 ``` 53 4 54 1 0 0 1 55 ``` 56 57 Output 58 59 ``` 60 4 61 ``` 62 63 Note 64 65 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]. 66 67 In the second case, flipping only the second and the third element (*i* = 2, *j* = 3) will turn all numbers into 1.