← 返回题目列表

Codeforces · 327/A

A. 翻转游戏

中文机器翻译题面 查看原题

Iahub 觉得无聊,所以他发明了一种在纸上玩的游戏。

他写了 n 个整数 a1, a2, ..., an。这些整数中的每一个都可以是 0 或 1。他只能执行一次移动:他选择两个索引 i 和 j (1 ≤ i ≤ j ≤ n) 并翻转其位置在 [i, j] 范围内(即 i ≤ k ≤ j)的所有值 ak。翻转 x 的值意味着应用 x = 1 - x 运算。

游戏的目标是在恰好走完一步后获得最大数量的 1。编写一个程序来解决Iahub的小游戏。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 100)。输入的第二行有 n 个整数:a1, a2, ..., an。保证这 n 个值中的每一个都是 0 或 1。

输出

打印一个整数 — 一次移动后可获得的 1 的最大数量。

示例

输入 #1

5
1 0 0 1 0

输出 #1

4

输入 #2

4
1 0 0 1

输出 #2

4

注意

在第一种情况下,将段从 2 翻转到 5 (i = 2, j = 5)。翻转改变了顺序,它变成:[1 1 1 0 1]。所以,它包含四个。没有办法让整个序列等于[1 1 1 1 1]。

在第二种情况下,仅翻转第二个和第三个元素(i = 2,j = 3)会将所有数字变为 1。