सरणी दी गई है जिसमें प्रत्येक तत्व अधिकतम दो बार आता है। दो उपसमुच्चय बनाएं जिनमें कोई पुनरावृत्ति न हो और उनके योग का अंतर अधिकतम हो।
रणनीति: एकल घटना वाले तत्वों को उनके चिह्न के आधार पर अलग करें। धनात्मक को एक उपसमुच्चय में, ऋणात्मक को दूसरे में। दोहरे तत्वों को अनदेखा करें (वे अंतर में योगदान नहीं देते)।
उदाहरण: {4, 2, -3, 3, -2, -2, 8} → अधिकतम अंतर 20।
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
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