ความแตกต่างสูงสุดที่เป็นไปได้ของสองชุดย่อยของอาร์เรย์ใน 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