Negatives and Positives (Codeforces 1791E)
Tags: Greedy, sortings

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}$$$. 

Input: 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$$$.

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

Note: 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$$$.

Sample Inputs:
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

Sample Outputs:
1
13
6
39
2

Solution (Python):
for s in [*open(0)][2::2]:
    a = list(map(abs, map(int, s.split())))
    print(sum(a) - s.count('-') % 2 * 2 * min(a))

Solution (Python):
def test():
    n = int(input())
    lst = list(map(int, input().split()))
    minus = 0
    for i in lst:
        if i < 0:
            minus += 1
    lst = list(map(abs, lst))
    if minus % 2 == 0:
        print(sum(lst))
    else:
        print(sum(lst) - min(lst) * 2)
for _ in range(int(input())):
    test()

Solution (Python):
for s in [*open(0)][2::2]:
    a = (*map(abs, map(int, s.split())),)
    print(sum(a) - s.count('-') % 2 * 2 * min(a))