সি++-এ সমান সংখ্যক ০ এবং ১ বিশিষ্ট সর্ববৃহৎ সাবঅ্যারে

একটি বাইনারি অ্যারেতে সমান সংখ্যক ০ এবং ১ বিশিষ্ট সর্বোচ্চ দৈর্ঘ্যের সাবঅ্যারে বের করতে হবে।

টেকনিক

০ কে -১ মনে করলে, সমান ০ ও ১ মানে সাবঅ্যারে যোগফল ০।

অ্যালগরিদম

• অ্যারেতে ০ কে -১ বদলান।
• হ্যাশ ম্যাপ দিয়ে প্রিফিক্স সম সংরক্ষণ করুন।
• যদি একই সম দুবার পাওয়া যায়, মাঝপথের সাবঅ্যারে যোগফল ০।
• সর্বোচ্চ দৈর্ঘ্য ট্র্যাক করুন।

সি++ ইমপ্লিমেন্টেশন

#include <bits/stdc++.h>
using namespace std;

void findLargestSubarray(int arr[], int n) {
    unordered_map prefixIndex;
    int sum = 0, maxLen = 0, endIdx = -1;
    for (int i = 0; i < n; i++) arr[i] = (arr[i] == 0 ? -1 : 1);
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        if (sum == 0) { maxLen = i + 1; endIdx = i; }
        if (prefixIndex.count(sum)) {
            if (i - prefixIndex[sum] > maxLen) {
                maxLen = i - prefixIndex[sum];
                endIdx = i;
            }
        } else prefixIndex[sum] = i;
    }
    cout << endIdx - maxLen + 1 << " " << endIdx << endl;
}

int main() {
    int arr[] = {1, 1, 0, 0, 0, 1, 1, 1, 0};
    findLargestSubarray(arr, 9); // আউটপুট: 1 8
    return 0;
}

আউটপুট

1 8