# [Solution] Plusle and Minun on Array solution codechef

Plusle and Minun on Array solution codechef – Chef has an array AA of length NN. He defines the alternating sum of the array as:

• S=|A1||A2|+|A3||A4|+(1)N1|AN|S=|A1|−|A2|+|A3|−|A4|+…(−1)N−1⋅|AN|

Chef is allowed to perform the following operation on the array at most once:

• Choose two indices ii and jj (1i<jN)(1≤i<j≤N) and swap the elements AiAi and AjAj.

# Plusle and Minun on Array solution codechef

Find the maximum alternating sum Chef can achieve by performing the operation at most once.

Note: |X||X| denotes the absolute value of XX. For example, |4|=4|−4|=4 and |7|=7|7|=7.

### Input Format

• The first line will contain TT – the number of test cases. Then the test cases follow.
• First line of each test case contains a single integer NN – size of the array AA.
• Second line of each test case contains NN space separated integers – denoting the elements of array AA.

### Output Format

For each testcase, output in a single line, the maximum alternating sum Chef can obtain by performing the operation at most once.

## Plusle and Minun on Array solution codechef

• 1T1051≤T≤105
• 2N1052≤N≤105
• 109Ai109−109≤Ai≤109
• Sum of NN over all test cases does not exceed 21052⋅105.

### Sample Input 1

2
2
10 -10
7
-3 -2 -1 0 1 2 3


### Plusle and Minun on Array solution codechef

0
6


### Plusle and Minun on Array Explanation

Test Case 11: One optimal way is to perform no operations. Thus the alternating sum is |10||10|=1010=0|10|−|−10|=10−10=0.

Test Case 22: One optimal way is to choose i=2i=2 and j=5j=5. After swapping, the array is [3,1,1,0,2,2,3][−3,1,−1,0,−2,2,3]. The alternating sum in this case is |3||1|+|1||0|+|2||2|+|3|=6|−3|−|1|+|−1|−|0|+|−2|−|2|+|3|=6.