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