← 返回比赛

已结束 GESP欢乐赛#30

← 上一题下一题 →

A4543 | $摇摇晃摇$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给你一个由 $n$ 个整数 $a_1, a_2, \ldots, a_n$ 组成的数组。这些整数不是 $1$ 就是 $-1$ 。你必须对数组 $a$ 执行一次以下操作： - 选择一个索引 $i$ ( $1 \leq i \leq n$ )，然后翻转 $a_i$ 和 $a_{i+1}$ 的符号。翻转符号会将数值从$-1$ 变为 $1$ 或者将 $1$ 变为 $-1$ 。 进行上述运算后， $a_1 + a_2 + \ldots + a_n$ 的最大值是多少？

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \le t \le 500$ )。测试用例说明如下。 每个测试用例的第一行包含一个整数 $n$ ( $2 \le n \le 10^5$ )，即数组的长度 $a$ 。 下一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （ $a_i = 1$ 或 $a_i = -1$ ）。 所有情况下 $n$ 的总和不超过 $10^5$ 。

输出格式

对于每个测试用例，单独一行打印数组 $a$ 的最大总和。

输入输出样例

输入 #1

4
5
-1 1 1 -1 -1
5
1 1 -1 -1 -1
2
1 1
4
1 -1 -1 1

输出 #1

C++ 编辑器

输入

输出