Maximum sum of absolute difference

Easy

0/40

10 upvotes

Asked in companies

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.

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

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.

Sample Input 1 :

Sample Output 1 :

16
12

Explanation of The Sample Input 1:

For the first test case:

The given array is : {1,2,8,3} for this array the maxSum will be of the permutation {1,8,2,3} which gives us maxSum = |1-8| + |2-8| + |8-3| + |3-1| = 16. So, we will return 16.  

For the second test case:

The given array is : {1,2,3,4,5} for this array the maxSum will be of the permutation {3,4,2,5,1} which gives us maxSum = |3-4| + |4-2| + |2-5| + |5-1| + |1-3| = 12. So, we will return 16.

Sample Input 2 :

2
6
3 4 2 9 1 5
2
1 3

Sample Output 2 :

24
4

Hint 1

Can you solve it greedily?

Approaches (1)

Approach 1

Greedy

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.

Time Complexity

O(N * log(N)), where ‘N’ denotes the length of the array.

Since we are sorting the array so time complexity for sorting will be O(N * log(N)). The time required for traversing the array will be O(N). Therefore, the net time complexity will be O(N * log(N)) + O(N) = O(N * log(N)).

Space Complexity

O(N), where ‘N’ denotes the length of the array.

Since we are creating a new array to store all the elements of the given array.

(100% EXP penalty)

Maximum sum of absolute difference

Console