Greedy: Maximum sum of absolute difference of an array

Problem Statement:

You are given an array, you need to find the maximum sun of absolute difference of any permutation in the given array.

Example

Input: 1, 2, 7

Output: 11

Explanation:

sum = |1 – 7| + |7 – 2| = 11.

So the arrangement is (1, 7, 2)

Solution

We can solve this problem with the help of greedy approach.

We need to re-arrange the elements so that the sum is maximum.

So we can get it by take a difference between a smaller element with a largest element.

Steps:

1. Sort the array

2. Now take the smallest element and largest element and put in an array.

3. Calculate the sum of absolute difference between the elements of the array.

Solution in C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;

int get_max_sum(vector<int> &a, int n)
{
    vector<int> finalSequence;

    sort(a.begin(), a.end());
  
    for (int i = 0; i < n / 2; ++i) 
    {
        finalSequence.push_back(a[i]);
        finalSequence.push_back(a[n - i - 1]);
    }

    //if the vector is having odd elements then
    //push the middle element to the end.
    if (n % 2 != 0)
        finalSequence.push_back(a[n/2]);

    int MaximumSum = 0;
  
    for (int i = 0; i < n - 1; ++i) 
    {
        MaximumSum = MaximumSum + abs(finalSequence[i] - 
                                  finalSequence[i + 1]);
    }
  
    MaximumSum = MaximumSum + abs(finalSequence[n - 1] -
                                      finalSequence[0]);
  
    return MaximumSum;
}
  
int main()
{
    vector<int> arr = { 1, 7, 2, 3 };
    int n = arr.size();
  
    cout <<"The max sum is = "<< get_max_sum(arr, n) << endl;
}

Output:

The max sum is = 14

			
Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *