Codeforces Round 849 (Div. 4) |
---|
Finished |
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:
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.
53-1 -1 -151 5 -5 0 231 2 36-1 10 9 8 7 62-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$$$.
Name |
---|