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개의 최소 요소를 하위 시퀀스에 대해 고려하는 경우 최대 가중치 차이, 즉 요소의 합과 나머지의 차이가 최대라는 사실을 사용하여 보다 효율적인 솔루션을 찾을 수 있습니다.

따라서 우리는 mlargest 요소의 부분 시퀀스와 m개의 가장 작은 요소 및rest 배열의 나머지 배열 또는 부분 시퀀스에 대한 최대 합계 차이를 확인합니다.

그리고 둘 다의 최대값을 반환합니다.

알고리즘

초기화 -

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

출력

The maximum weight difference is 15