C++ 程序中的最大权重差异

在这个问题中，我们得到一个数组 arr[] 和一个数字 M。我们的任务是创建一个程序来计算 C++ 中的最大权重差异。

问题描述

We will find M elements from the array such that the absolute difference
between the sum and the sum of the rest elements is maximum.

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

输入

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

输出结果

15

解释

我们将考虑 4、6、9。总和为 19。与其余数总和的绝对差为

|19 − 4| = 15

解决方法

该问题的一个简单解决方案是找到数组的所有子序列，找到子数组的和元素，以及其余的元素。并返回最大差值。

如果我们为子序列考虑 m 个最大元素或 m 个最小元素，则通过使用最大权重差异即元素总和与其余元素的差异最大这一事实找到更有效的解决方案。

因此，我们将检查 m 个最大元素和剩余数组的子序列或 m 个最小元素和剩余数组的子序列的最大和差。

并返回两者的最大值。

算法

初始化-

maxSum , maxSumDiff, minSumDiff

步骤 1 -

sort the array in descending order.

第 2 步-

Loop for i −> 0 to n

步骤 2.1 -

if (i < m) −> maxSumDiff += arr[i]

步骤 2.2 -

else −> maxSumDiff −= arr[i]

第 2 步-

Loop for i −> n to 0

步骤 2.1 -

if (i > m) −> minSumDiff += arr[i]

步骤 2.2 -

else −> minSumDiff −= arr[i]

第 3 步-

if maxSumDiff > minSumDiff −> maxSum = maxSumDiff.

第 4 步-

if maxSumDiff < minSumDiff −> maxSum = minSumDiff.

第 5 步-

return maxSum.

示例

程序来说明我们的解决方案的工作，

#include <bits/stdc++.h>
using namespace std;
int maxWeightDifference(int arr[], int N, int M){
   int maxabsDiff = −1000;
   sort(arr, arr + N);
   int sumMin = 0, sumMax = 0, arrSum = 0;
   for(int i = 0; i < N; i++){
      arrSum += arr[i];
      if(i < M)
         sumMin += arr[i];
      if(i >= (N−M))
         sumMax += arr[i];
   }
   maxabsDiff = max(abs(sumMax − (arrSum − sumMax)), abs(sumMin −
   (arrSum − sumMin)));
   return maxabsDiff;
}
int main(){
   int arr[] = {3, 1, 6, 9, 4} ;
   int M = 3;
   int N = sizeof(arr)/sizeof(arr[0]);
   cout<<"最大重量差为 "<<maxWeightDifference(arr,N, M);
   return 0;
}

输出结果

最大重量差为 15