C++-এ অ্যারেতে দুটি সাবসেটের পার্থক্য সর্বোচ্চ করার প্রোগ্রাম

সমস্যা বিবরণ

একটি অ্যারে দেওয়া থাকলে (প্রতিটি সংখ্যা এক বা দুবার থাকতে পারে), দুটি সাবসেট বানাতে হবে যাতে: 1. কোনো সাবসেটে ডুপ্লিকেট নয়। 2. দুটি সাবসেটের সমের পার্থক্য সর্বোচ্চ হয়।

সমাধানের পদ্ধতি

1. যে সংখ্যাগুলো একবার আছে (unique), সেগুলো পজেটিভ হলে সাবসেট ১-এ, নেগেটিভ হলে সাবসেট ২-এ নিন।
2. যে সংখ্যাগুলো দুবার আছে, সেগুলোকে ০ করুন (কারণ একটি সাবসেটে একবারই নেওয়া যাবে, পার্থক্যতে কন্ট্রিবিউট করবে না)।
3. উত্তর = |SubsetSum₁ - SubsetSum₂|।

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

ব্যাখ্যা

অ্যারে: 4, 2, -3, 3, -2, -2, 8

ডুপ্লিকেট: -2 (দুবার) → ০ করে দিলে: 4, 2, -3, 3, 0, 0, 8

সাবসেট ১ (পজেটিভ): 4 + 2 + 3 + 8 = 17

সাবসেট ২ (নেগেটিভ): -3

পার্থক্য = |17 - (-3)| = 20

জটিলতা

• সময়: O(n²) — নেস্টেড লুপ (অপ্টিমাইজ করা যায় O(n) হ্যাশম্যাপ দিয়ে)
• স্থান: O(1)