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