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