Last Updated: 10 Feb, 2021

Maximum sum of absolute difference

Easy

Asked in companies

Solve now

Problem statement

You are given an array, your task is to find the maximum sum of absolute difference of adjacent numbers of any permutation of the given array.

Note

The first and the last number of the array are adjacent to each other.

Example

The given array is {3, 6, 8, 4, 5}. So you have to consider all the permutations of this array like one of the permutations of this array is {6, 3, 5, 4, 8}. For this permutation answer will be sum of absolute difference of adjacent elements that is maxSum = |6-3| + |3-5| + |5-4| + |4-8| + |8-6| = 12 and for another permutation, say {3, 8, 4, 6, 5}, maxSum = |3-8| + |8-4| + |4-6| + |6-5| + |5-3| = 14. In this case, it will be the maximum of all permutations. So the answer will be 14.

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the length of the array.
The second line of each test contains N space-separated integers representing the elements of the given array.

Output format :

For each test case, in a separate line, print the maximum sum of the absolute difference of any permutation of the given array.

Note:

You don’t have to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 10000
1 <= arr[I] <= 10^6
 where ‘T’ is the total number of test cases, N is the length of the array and arr[I] is the value at index ‘I’ of the array.

Solve now

Approaches

01 Approach

The idea is to keep the difference between any two adjacent numbers maximum. This can be achieved if we put small and large elements alternatively.

For this, first, sort the given array.
Declare a new array and add elements to it by taking the elements of the sorted array.
That is, first insert the first element of the array then the last element, then the second element, then the second last, and so on until all the elements of the array are inserted.
Finally, calculate the sum of the absolute difference between the elements of the new array by subtracting the adjacent elements and taking their absolute value.
Finally, return the answer obtained by doing the above step.

Solve now