← 返回题目列表

Codeforces · 1778/A

A. 触发器总和

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

给你一个 $$$n$$$ 整数数组 $$$a_1, a_2, \ldots, a_n$$$。整数为 $$$1$$$ 或 $$$-1$$$。您必须对数组 $$$a$$$ 执行一次以下操作:

- 选择一个索引 $$$i$$$ ($$$1 \leq i < 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

3
3
-2
4

注意

在第一种情况下,我们可以选择索引 $$$4$$$ 并翻转 $$$a_4$$$ 和 $$$a_5$$$ 的符号。执行此操作后,总和将为 $$$-1+1+1+1+1 = 3$$$。我们不能使总和大于这个。

在第三种情况下,唯一的选择是选择索引$$$1$$$。