C++ 中任意排列绝对差的最大和
c++server side programmingprogramming
本题中，给定一个数组。我们的任务是编写一个程序，用 C++ 求任意排列绝对差的最大和。
问题描述
我们将求出给定数组元素的所有排列。然后求出数组中相邻元素绝对差的和。最后，我们将返回所有和中的最大值。
我们举个例子来理解这个问题:
输入
arr[] = {9, 1, 6, 3}
输出
17
解释
数组的所有排列，相邻元素的绝对差之和为该排列的和。
{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 − 最后，返回最大和。
示例
编写程序来说明我们的解决方案的工作原理，
#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<<"任何排列的最大绝对差和是 "<<calcMaxSumAbsDiff(arr, N);
}
输出
任何排列的最大绝对差和是 22
