বাইনারি ম্যাট্রিক্সে ১-এর গণনা ০-এর চেয়ে এক বেশি হলে সর্বোচ্চ সাব-ম্যাট্রিক্স এলিয়া (C++ প্রোগ্রাম)

এই সমস্যাতে, আমাদের n×n আকারের একটি 2-D ম্যাট্রিক্স দেওয়া আছে যেটি বাইনারি সংখ্যা (০/১) ধারণ করে। আমাদের কাজ হল ১-এর গণনা ০-এর চেয়ে এক বেশি হলে সর্বোচ্চ সাব-ম্যাট্রিক্স এলিয়া খুঁজে বের করার প্রোগ্রাম তৈরি করা।

bin[N][N] = { {0, 1, 0, 0}, {1, 1, 0, 0}, {1, 0, 1, 1}, {0, 1, 0, 1} }

9

সাবম্যাট্রিক্স: bin[1][0], bin[1][1], bin[1][2]
bin[2][0], bin[2][1], bin[2][2]
bin[3][0], bin[3][1], bin[3][2]
এটি ০-এর চেয়ে ১ বেশি ১ সহ সবচেয়ে বড় সাবঅ্যারে।
০-এর সংখ্যা = ৪
১-এর সংখ্যা = ৫

একটি সহজ পদ্ধতি হল ম্যাট্রিক্স থেকে সব সম্ভাব্য সাবম্যাট্রিক্স বের করে সর্বোচ্চ এলিয়া ফেরত দেওয়া। এই পদ্ধতি ভাবা এবং বাস্তবায়ন করা সহজ হলেও এতে অনেক সময় লাগে এবং লুপ নেস্টিং এর কারণে এর টাইম কমপ্লেক্সিটি O(n⁴) হয়। তাই আসুন আরেকটি আরও কার্যকর পদ্ধতি আলোচনা করি।

এখানে আইডিয়া হল ম্যাট্রিক্সের বাম এবং ডান কলাম ফিক্স করে তারপর সবচেয়ে বড় সাবঅ্যারে খুঁজে বের করা যেটিতে ০-এর সংখ্যা ১-এর চেয়ে এক বেশি। আমরা প্রতিটি সারিতে যোগফল হিসাব করব এবং তারপর সেটি কিউমুলেট করব। ১-এর গণনা ০-এর চেয়ে এক বেশি হওয়ার সর্বোচ্চ এলিয়া বের করার জন্য।

#include 
using namespace std;

#define SIZE 10

int lenOfLongSubarr(int row[], int n, int& startInd, int& finishInd) {
    unordered_map subArr;
    int sumVal = 0, maxSubArrLen = 0;
    for (int i = 0; i < n; i++) {
        sumVal += row[i];
        if (sumVal == 1) {
            startInd = 0;
            finishInd = i;
            maxSubArrLen = i + 1;
        } else if (subArr.find(sumVal) == subArr.end())
            subArr[sumVal] = i;
        
        if (subArr.find(sumVal - 1) != subArr.end()) {
            int currLen = (i - subArr[sumVal - 1]);
            if (maxSubArrLen < currLen) {
                startInd = subArr[sumVal - 1] + 1;
                finishInd = i;
                maxSubArrLen = currLen;
            }
        }
    }
    return maxSubArrLen;
}

int largestSubmatrix(int bin[SIZE][SIZE], int n) {
    int rows[n], maxSubMatArea = 0, currArea, longLen, startInd, finishInd;
    for (int left = 0; left < n; left++) {
        memset(rows, 0, sizeof(rows));
        for (int right = left; right < n; right++) {
            for (int i = 0; i < n; ++i) {
                if (bin[i][right] == 0)
                    rows[i] -= 1;
                else
                    rows[i] += 1;
            }
            longLen = lenOfLongSubarr(rows, n, startInd, finishInd);
            currArea = (finishInd - startInd + 1) * (right - left + 1);
            if ((longLen != 0) && (maxSubMatArea < currArea)) {
                maxSubMatArea = currArea;
            }
        }
    }
    return maxSubMatArea;
}

int main() {
    int bin[SIZE][SIZE] = {
        { 1, 0, 0, 1 },
        { 0, 1, 1, 1 },
        { 1, 0, 0, 0 },
        { 0, 1, 0, 1 }
    };
    int n = 4;
    cout << "The maximum sub-matrix area having count of 1's one more than count of 0's is " << largestSubmatrix(bin, n);
    return 0;
}

The maximum sub-matrix area having count of 1's one more than count of 0's is 9