Swap And Maximise

Easy

0/40

Average time to solve is 10m

Contributed by

6 upvotes

Asked in companies

Problem statement

You are given a circular array consisting of N integers. You have to find the maximum sum of the absolute difference between adjacent elements with rearrangement of array element allowed i.e after rearrangement of element find the maximum value of |a1 – a2| + |a2 – a3| + …… + |an – 1– an| + |an – a1|, where a1, a2, a3… an are the elements of the array.

An array is a circular array when after the last element 'an', 'a1' appears in the array.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line of the input contains an integer 'T' denoting the number of test cases. The 'T' test cases follow.

The first line of each test case contains an integer 'N', the size of the array.

The second line of each test case contains N space-separated integers representing the elements of the array.

Output Format :

The only line of output of each test case consists of an integer, denoting the maximum sum of the given array according to the given conditions. 

The output of each test case will be printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5
1 <= N <= 5000
1 <= ARR[i] <= 10^5

Where 'ARR[i]' is the value of any element of the array.

Time Limit: 1 sec

Sample Input 1 :

Sample Output 1 :

12
24

Explanation for Sample Output 1 :

For the first test case:    
To maximise the sum, one of the possible configurations is 2 7 4 5 and the maximum sum possible for the first input is 12.

For the second test case:
To maximise the sum, one of the possible configurations is 1 8 2 7 6 and the maximum sum possible for the second array is 24.

Sample Input 2 :

1
6
4 10 1 2 9 8

Sample Output 2 :

Console