C ++中任何排列的绝对差的最大和

在这个问题上，我们得到一个数组。我们的任务是创建一个程序，以查找C ++中任何排列的绝对绝对值的最大和。

问题描述

我们将找到给定数组元素的所有排列。然后找到数组相邻元素的绝对差之和。最后，我们将返回所有金额的最大值。

让我们举个例子来了解这个问题，

输入值

arr[] = {9, 1, 6, 3}

输出结果

17

说明

All permutations of the array with sum of absolute difference of adjacent elements.
{9, 1, 6, 3},
sum= |9-1| + |1-6| + |6-3| + |3-9| = 8+5+3+6 = 16
{9, 1, 3, 6},
sum= |9-1| + |1-3| + |3-6| + |6- 9| = 8+2+3+3 = 16
{9, 6, 1, 3},
sum= |9-6| + |6-1| + |1-3| + |3 - 9| = 3+5+2+6 = 16
{9, 6, 3, 1},
sum= |9-6| + |6-3| + |3-1| + |1 - 9| = 3+3+2+8 = 16
{9, 3, 1, 6},
sum= |9-3| + |3-1| + |1-6| + |6- 9| = 6+2+5+3 = 16
{9, 3, 6, 1},
sum= |9-3| + |3-6| + |6-1| + |1- 9| = 6+3+5+8 = 22
{1, 9, 6, 3},
sum= |1-9| + |9-6| + |6-3| + |3-1| = 8+3+3+2 = 16
{1, 9, 3, 6},
sum= |1-9| + |9-3| + |3-6| +
|6 - 1| = 8+6+3+5 = 22
{1, 6, 9, 3},
sum= |1-6| + |6-9| + |9-3| + |3 - 1| = 5+3+6+2 = 16
{1, 6, 3, 9},
sum= |1-6| + |6-3| + |3-9| + |9-1| = 5+3+6+8 = 22
{1, 3, 9, 6},
sum= |1-3| + |3-9| + |9-6| + |6-1| = 2+6+3+5 = 16
{1, 3, 6, 9},
sum= |1-3| + |3-6| + |6-9| + |9 - 1| = 2+3+3+8 = 16
..

所有采用6和3的排列都是起始数字。

解决方法

通过找到最大化解决方案的最佳方法，可以找到解决问题的简单方法。为了最大化解决方案，我们需要找到数组的所有最大绝对差。这可以使用|最小-最高|的绝对差来找到。

算法

步骤1-对数组进行排序。

步骤2-现在，通过将排序数组的最小数和最大数之间的绝对差相加来计算最大和。

步骤3-最后，返回maxSum。

示例

该程序说明了我们解决方案的工作原理，

#include <bits/stdc++.h>
using namespace std;
int calcMaxSumAbsDiff(int arr[], int N){
   int maxSumArray[N];
   int j = 0, maxSum = 0;
   sort(arr, arr + N);
   for (int i = 0; i < (N/2); ++i){
      maxSumArray[j] = arr[i];
      maxSumArray[j+1] = arr[N - i - 1];
      j += 2;
   }
   if (N % 2 != 0)
      maxSumArray[j] = arr[N/2];
   for (int i = 0; i < N - 1; i++){
      maxSum += abs(maxSumArray[i] - maxSumArray[i + 1]);
   }
   maxSum += abs(maxSumArray[N - 1] - maxSumArray[0]);
   return maxSum;
}
int main(){
   int arr[] = {9, 1, 6, 3};
   int N = sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum sum of absolute difference of any permutation is "<<calcMaxSumAbsDiff(arr, N);
}

输出结果

The maximum sum of absolute difference of any permutation is 22