Last Updated: 11 Feb, 2021
Swap And Maximise
Easy
Asked in companies
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.
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
Approaches
- The simplest possible approach will be to sort the array in non-decreasing order and find the answer.
- Since we want to maximize the overall sum of adjacent elements, we can try to bring the elements with greater difference closer.
- In order to do that, we have to arrange the elements in the following order a(1), a(n), a(2), a(n - 1), ….., a(n/2), a(n/2) + 1.
- Out of all the possible combinations, we will get the maximum sum using the above permutation.
- In this permutation, we can observe that elements a1, a2, a3… a(n/2) - 1, a(n/2) are subtracted twice while a(n/2) + 1, a(n/2) + 2, … , a (n - 1), a(n) are added twice.
- We also have to keep in mind that the term a(n/2) + 1 is considered only when n is even because when n is odd, it is added once and subtracted once so it cancels out.