इस समस्या में, हमें nXn आकार का 2-डी मैट्रिक्स दिया गया है जिसमें बाइनरी नंबर (0/1) है। हमारा काम अधिकतम सबमैट्रिक्स क्षेत्र को खोजने के लिए एक प्रोग्राम बनाना है जिसमें 0 की गिनती से 1 की गिनती अधिक हो।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
bin[N][N] = {
{0, 1, 0, 0},
{1, 1, 0, 0},
{1, 0, 1, 1},
{0, 1, 0, 1}
} आउटपुट
9
स्पष्टीकरण
submatrix : 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] is the largest subarray with more 1’s one more than 0’s. Number of 0’s = 4 Number of 1’s = 5
समाधान दृष्टिकोण
एक आसान तरीका यह है कि मैट्रिक्स से सभी संभव सबमैट्रिस ढूंढे जाएं और फिर सभी में से अधिकतम क्षेत्र लौटाएं।
इस दृष्टिकोण को सोचना और कार्यान्वित करना आसान है, लेकिन इसमें बहुत समय लगता है और इसके लिए लूपों के नेस्टिंग की आवश्यकता होती है जो ऑर्डर की समय जटिलता को बढ़ाता है O(n^4) .तो, आइए एक और विधि पर चर्चा करें जो अधिक प्रभावी है।
यहां विचार मैट्रिक्स के बाएं और दाएं कॉलम को ठीक करना है और फिर सबसे बड़ा सबरेरे ढूंढना है जिसमें 0 की संख्या 1 की संख्या से अधिक है। हम प्रत्येक पंक्ति में योग की गणना करेंगे और फिर इसे संचित करेंगे। 0 की संख्या से 1 की एक अधिक संख्या वाले अधिकतम क्षेत्र को खोजने के लिए।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
int lenOfLongSubarr(int row[], int n, int& startInd, int& finishInd){
unordered_map<int, int> 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