A15578 | $Flip Flop Sum$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

C++ 编辑器

输入

输出