C++ में 1 की संख्या 0 से एक अधिक होने वाले अधिकतम सब-मैट्रिक्स क्षेत्र

इस ट्यूटोरियल में, हम 1 की संख्या 0 से एक अधिक होने वाले अधिकतम सब-मैट्रिक्स क्षेत्र को खोजने के लिए एक प्रोग्राम पर चर्चा करेंगे।

इसके लिए हमें 0 और 1 वाली एक मैट्रिक्स प्रदान की जाएगी। हमारा कार्य 0 से अधिक 1 वाले अधिकतम क्षेत्र के सब-मैट्रिक्स को प्राप्त करना है।

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 
#define SIZE 10 
// सबसे लंबे सब-मैट्रिक्स की लंबाई ढूंढना 
int lenOfLongSubarr(int arr[], int n, int& start, int& finish) { 
    unordered_map<int, int> um; 
    int sum = 0, maxLen = 0; 
    for (int i = 0; i < n; i++) { 
        sum += arr[i]; 
        if (sum == 1) { 
            start = 0; 
            finish = i; 
            maxLen = i + 1; 
        } 
        else if (um.find(sum) == um.end()) um[sum] = i; 
        if (um.find(sum - 1) != um.end()) { 
            if (maxLen < (i - um[sum - 1])) 
                start = um[sum - 1] + 1; 
            finish = i; 
            maxLen = i - um[sum - 1]; 
        } 
    } 
    return maxLen; 
} 
// अधिकतम क्षेत्र ढूंढना 
void largestSubmatrix(int mat[SIZE][SIZE], int n) { 
    int finalLeft, finalRight, finalTop, finalBottom; 
    int temp[n], maxArea = 0, len, start, finish; 
    for (int left = 0; left < n; left++) { 
        memset(temp, 0, sizeof(temp)); 
        for (int right = left; right < n; right++) { 
            for (int i = 0; i < n; ++i) 
                temp[i] += mat[i][right] == 0 ? -1 : 1; 
            len = lenOfLongSubarr(temp, n, start, finish); 
            if ((len != 0) && (maxArea < (finish - start + 1) * (right - left + 1))) { 
                finalLeft = left; 
                finalRight = right; 
                finalTop = start; 
                finalBottom = finish; 
                maxArea = (finish - start + 1) * (right - left + 1); 
            } 
        } 
    } 
    cout << "(Top, Left): (" << finalTop << ", " << finalLeft << ")\n"; 
    cout << "(Bottom, Right): (" << finalBottom << ", " << finalRight << ")\n"; 
    cout << "Maximum area: " << maxArea; 
} 
int main() { 
    int mat[SIZE][SIZE] = { 
        { 1, 0, 0, 1 }, 
        { 0, 1, 1, 1 }, 
        { 1, 0, 0, 0 }, 
        { 0, 1, 0, 1 } 
    }; 
    int n = 4; largestSubmatrix(mat, n); 
    return 0; 
}

आउटपुट

(Top, Left): (1, 1) (Bottom, Right): (3, 3) Maximum area: 9