Flip Flop Sum

题意翻译

给定一个长度为 $n$ 的只含有 $1$ 或 $-1$ 的数组 $a$，对其进行如下的操作： - 选定一个 $i$，满足 $1\le i<n$，将 $a_i$ 修改为 $-a_i$，将 $a_{i+1}$ 修改为 $-a_{i+1}$。 求出一次操作之后 $\sum\limits_{i=1}^n a_i$ 的最大值。 by @zfx1569_HCl_2023

题目描述

You are given an array of $ n $ integers $ a_1, a_2, \ldots, a_n $ . The integers are either $ 1 $ or $ -1 $ . You have to perform the following operation exactly once on the array $ a $ : - Choose an index $ i $ ( $ 1 \leq i < n $ ) and flip the signs of $ a_i $ and $ a_{i+1} $ . Here, flipping the sign means $ -1 $ will be $ 1 $ and $ 1 $ will be $ -1 $ . What is the maximum possible value of $ a_1 + a_2 + \ldots + a_n $ after applying the above operation?

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). Description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 10^5 $ ), the length of the array $ a $ . The next line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ a_i = 1 $ or $ a_i = -1 $ ). The sum of $ n $ over all cases doesn't exceed $ 10^5 $ .

输出格式

For each test case, print the maximum possible sum of the array $ a $ you can get in a separate line.

输入输出样例

输入样例 #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

说明

In the first case, we can choose index $ 4 $ and flip the signs of $ a_4 $ and $ a_5 $ . After this operation, the sum will be $ -1+1+1+1+1 = 3 $ . We can't make the sum larger than this. In the third case, the only option is to choose the index $ 1 $ .

题目大意：
给定一个长度为 $n$ 的只含有 $1$ 或 $-1$ 的数组 $a$，进行一次如下操作：
- 选定一个 $i$，满足 $1\le i 求出一次操作之后 $\sum\limits_{i=1}^n a_i$ 的最大值。

输入输出数据格式：
输入格式：
每个测试包含多个测试用例。第一行包含测试用例的数量 $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$ 可能得到的最大和。题目大意： 给定一个长度为 $n$ 的只含有 $1$ 或 $-1$ 的数组 $a$，进行一次如下操作： - 选定一个 $i$，满足 $1\le i