题目描述

桌上有 \(n\) 枚硬币，状态互不相同，我们以 \(1,0\)（\(1\) 为正面，\(0\) 为反面） 来表示它们是否是正面朝上。现在我们有一次机会选择 \(i,j（1≤i≤j≤n）\)，把 \([i,j]\) 范围内（包括 \(i\) 和 \(j\)）的所有硬币翻转过来（翻转的含义是：\(1->0,0->1\)）。计算最多一次翻转后（允许不翻转），最多有多少枚硬币正面朝上。

格式

输入格式

第一行为正整数 \(t(≤10)\)，表示数据组数；每组数据中，第一行为正整数 \(n(≤ 10^5)\)，表示硬币数；第二行为 \(n\) 个 \(0\) 和 \(1\)，以空格隔开，分别表示每枚硬币的初始状态。

输出格式

对于每组数据，输出最多一次翻转后，正面朝上硬币的最大数。

样例1

样例输入1

2
5
1 0 0 1 0
4
1 0 0 1

样例输出1

4
4

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T4\)

文件IO

freopen("flip.in","r",stdin);
freopen("flip.out","w",stdout);