इस समस्या में, हमें n×n आकार का एक 2-D मैट्रिक्स दिया गया है जिसमें बाइनरी संख्याएं (0/1) हैं। हमारा कार्य एक प्रोग्राम बनाना है जो अधिकतम उप-मैट्रिक्स क्षेत्र ढूंढे जहां 1 की गिनती 0 से एक अधिक हो।
उदाहरण
इनपुट
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] अधिक 1 वाले सबसे बड़े उपसरणी में 0 से एक अधिक। 0 की संख्या = 4 1 की संख्या = 5
समाधान दृष्टिकोण
एक सरल दृष्टिकोण मैट्रिक्स से सभी संभावित उपमैट्रिक्स ढूंढना और फिर सभी में से अधिकतम क्षेत्र वापस करना है।
यह दृष्टिकोण सोचने और लागू करने में आसान है लेकिन बहुत समय लेता है और लूप के नेस्टिंग की आवश्यकता होती है जो इसकी समय जटिलता को O(n^4) क्रम का बना देता है। तो, आइए एक और विधि पर चर्चा करें जो अधिक प्रभावी है।
यहां विचार मैट्रिक्स के बाएं और दाएं कॉलम को ठीक करना है और फिर सबसे बड़ी उपसरणी ढूंढना है जिसमें 0 की संख्या 1 की संख्या से एक अधिक हो। हम प्रत्येक पंक्ति पर योग की गणना करेंगे और फिर इसे संचयी करेंगे। 1 की गिनती 0 से एक अधिक होने वाले अधिकतम क्षेत्र को ढूंढने के लिए।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
#include <bits/stdc++.h>
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
