Negatives and Positives

题意翻译

给你一个长度为 $n$ 的序列 $a$，你可以执行若干次如下操作： - 选择一个 $i(1\leq i<n)$，将 $a_i,a_{i+1}$ 取相反数。 求经过若干次操作后的 $\max\{\sum_{i=1}^n a_i\}$。

题目描述

Given an array $ a $ consisting of $ n $ elements, find the maximum possible sum the array can have after performing the following operation any number of times: - Choose $ 2 $ adjacent elements and flip both of their signs. In other words choose an index $ i $ such that $ 1 \leq i \leq n - 1 $ and assign $ a_i = -a_i $ and $ a_{i+1} = -a_{i+1} $ .

输入输出格式

输入格式

The input consists of multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. The descriptions of the test cases follow. The first line of each test case contains an integer $ n $ ( $ 2 \leq n \leq 2\cdot10^5 $ ) — the length of the array. The following line contains $ n $ space-separated integers $ a_1,a_2,\dots,a_n $ ( $ -10^9 \leq a_i \leq 10^9 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot10^5 $ .

输出格式

For each test case, output the maximum possible sum the array can have after performing the described operation any number of times.

输入输出样例

输入样例 #1

5
3
-1 -1 -1
5
1 5 -5 0 2
3
1 2 3
6
-1 10 9 8 7 6
2
-1 -1

输出样例 #1

1
13
6
39
2

说明

For the first test case, by performing the operation on the first two elements, we can change the array from $ [-1, -1, -1] $ to $ [1, 1, -1] $ , and it can be proven this array obtains the maximum possible sum which is $ 1 + 1 + (-1) = 1 $ . For the second test case, by performing the operation on $ -5 $ and $ 0 $ , we change the array from $ [1, 5, -5, 0, 2] $ to $ [1, 5, -(-5), -0, 2] = [1, 5, 5, 0, 2] $ , which has the maximum sum since all elements are non-negative. So, the answer is $ 1 + 5 + 5 + 0 + 2 = 13 $ . For the third test case, the array already contains only positive numbers, so performing operations is unnecessary. The answer is just the sum of the whole array, which is $ 1 + 2 + 3 = 6 $ .

题目大意：
给定一个由n个元素组成的数组a，你可以执行任意多次以下操作：
- 选择两个相邻的元素并将它们的符号取反。换句话说，选择一个索引i，使得1≤i≤n-1，并将ai=-ai和ai+1=-ai+1。

求经过若干次操作后的max{∑ni=1ai}。

输入输出数据格式：
输入格式：
输入由多个测试用例组成。第一行包含一个整数t（1≤t≤1000）——测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n（2≤n≤2×105）——数组的长度。
下一行包含n个由空格分隔的整数a1,a2,…,an（-109≤ai≤109）。
保证所有测试用例的n之和不超过2×105。
输出格式：
对于每个测试用例，输出执行描述的操作任意次后数组的最大可能和。题目大意： 给定一个由n个元素组成的数组a，你可以执行任意多次以下操作： - 选择两个相邻的元素并将它们的符号取反。换句话说，选择一个索引i，使得1≤i≤n-1，并将ai=-ai和ai+1=-ai+1。 求经过若干次操作后的max{∑ni=1ai}。 输入输出数据格式： 输入格式： 输入由多个测试用例组成。第一行包含一个整数t（1≤t≤1000）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（2≤n≤2×105）——数组的长度。 下一行包含n个由空格分隔的整数a1,a2,…,an（-109≤ai≤109）。 保证所有测试用例的n之和不超过2×105。 输出格式： 对于每个测试用例，输出执行描述的操作任意次后数组的最大可能和。