C++での最大重量差

この問題では、配列arr []と数値Mが与えられます。私たちのタスクは、C++での最大重み差を計算するプログラムを作成することです。

問題の説明

残りの要素の合計と合計の絶対差が最大になるように、配列からM個の要素を見つけます。

問題を理解するために例を見てみましょう

入力 ：arr [] ={3、1、6、9、4} M =3

出力 ：15

説明

4,6,9を検討します。合計は19です。残りの数の合計との絶対差は

| 19-4 | =15

ソリューションアプローチ

この問題の解決策は、最大の差がM個の最大数またはM個の最小数の場合にのみ可能であるという事実に基づいています。最終的な結果を見つけるには、両方の条件を確認し、絶対差を比較する必要があります。 M個の最大/最小数を見つけるプロセスを簡単にするために、配列を並べ替えてから、K個の最大数と最小数で計算を行います。

例

#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<<"The maximum weight difference is "<<maxWeightDifference(arr,N, M);
   return 0;
}

出力

The maximum weight difference is 15