Maximum sum of absolute difference of any permutation

December 30, 2021

Maximum sum of absolute difference of any permutation

In Maximum sum of absolute difference of any permutation we have to rearrange the array elements in such a way that the sum of absolute differences is largest possible. The problem can be solved using greedy technique. In this article, we will provide a C++ Solution with an explanation.

Maximum sum of absolute difference of any permutation Problem Description

Given an array of n integers. Rearrange the array elements such that the sum of absolute difference of adjacent elements is largest. Consider the array cyclic in nature. Output the largest sum possible.

Input

First Line contains a single integer – the size of the array.
Second-line contains n integers the array elements.

Output

The maximum sum.

Problem Solution

The problem can be solved using greedy technique. To get the maximum sum the permutation should be alternate sequence of minimum, maximum and so on. By this permutation we can maximize the consecutive difference as we paired the minimum value with the maximum value.

Time Complexity – O(nlogn)

Space Complexity – O(1)

Code

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;

    int arr[n];
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    sort(arr, arr + n);

    int permutation[n];

    int st = 0, ed = n – 1;

    for (int i = 0; i < n; i++)
    {
        if (i % 2 == 0)
        {
            permutation[i] = arr[st];
            st++;
        }
        else
        {
            permutation[i] = arr[ed];
            ed–;
        }
    }

    int ans = 0;

    ans = abs(permutation[n – 1] – permutation[0]);
    for (int i = 1; i < n; i++)
    {
        ans += abs(permutation[i] – permutation[i – 1]);
    }

    cout << ans << endl;
    return 0;
}

Output

4
1 2 4 8
18


Explanation
The permutation is 1 8 2 4