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 :

Hint 1

Try to use a greedy approach.

Approaches (1)

Approach 1

Greedy

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.

Time Complexity

O(N * log(N)), where N is the number of elements in the array.

Since we are sorting the array of size ‘N’, the time complexity will be O(N * logN).

Space Complexity

O(1).

We are using constant extra space.

(100% EXP penalty)

Swap And Maximise

Console