Sự khác biệt tối đa có thể có của hai tập con của một mảng trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm ra sự khác biệt tối đa có thể có của hai tập con của một mảng

Đối với điều này, chúng tôi sẽ được cung cấp một mảng chứa một hoặc hai trường hợp của một vài số nguyên ngẫu nhiên. Nhiệm vụ của chúng ta là tạo hai tập con của mảng đó sao cho hiệu của tổng của chúng là lớn nhất và không có tập con nào chứa các số lặp lại.

Ví dụ

#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;
}

Đầu ra

Maximum Difference = 20