1791E.md (2005B)
1 Source: https://codeforces.com/problemset/problem/1791/E 2 3 E. Negatives and Positives 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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: 22 23 * 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}$. 24 25 Input 26 27 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. 28 29 The first line of each test case contains an integer $n$ ($2 \leq n \leq 2\cdot10^5$) — the length of the array. 30 31 The following line contains $n$ space-separated integers $a_1,a_2,\dots,a_n$ ($-10^9 \leq a_i \leq 10^9$). 32 33 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$. 34 35 Output 36 37 For each test case, output the maximum possible sum the array can have after performing the described operation any number of times. 38 39 Example 40 41 Input 42 43 ``` 44 5 45 46 3 47 48 -1 -1 -1 49 50 5 51 52 1 5 -5 0 2 53 54 3 55 56 1 2 3 57 58 6 59 60 -1 10 9 8 7 6 61 62 2 63 64 -1 -1 65 ``` 66 67 Output 68 69 ``` 70 1 71 13 72 6 73 39 74 2 75 ``` 76 77 Note 78 79 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$. 80 81 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$. 82 83 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$.