C++에서 배열의 두 하위 집합의 가능한 최대 차이

이 자습서에서는 배열의 두 하위 집합에서 가능한 최대 차이를 찾는 프로그램에 대해 설명합니다.

이를 위해 소수의 임의 정수 인스턴스가 하나 또는 두 개 포함된 배열이 제공됩니다. 우리의 임무는 합계의 차이가 최대이고 하위 집합에 반복적인 숫자가 포함되지 않도록 해당 배열의 두 하위 집합을 만드는 것입니다.

예시

#include <bits/stdc++.h>
using namespace std;
//finding maximum subset difference
int maxDiff(int arr[], int n) {
   int SubsetSum_1 = 0, SubsetSum_2 = 0;
   for (int i = 0; i <= n - 1; i++) {
      bool isSingleOccurance = true;
      for (int j = i + 1; j <= n - 1; j++) {
         if (arr[i] == arr[j]) {
            isSingleOccurance = false;
            arr[i] = arr[j] = 0;
            break;
         }
      }
      if (isSingleOccurance) {
         if (arr[i] > 0)
            SubsetSum_1 += arr[i];
         else
            SubsetSum_2 += arr[i];
      }
   }
   return abs(SubsetSum_1 - SubsetSum_2);
}
int main() {
   int arr[] = { 4, 2, -3, 3, -2, -2, 8 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Maximum Difference = " << maxDiff(arr, n);
   return 0;
}

출력

Maximum Difference = 20