इस ट्यूटोरियल में, हम सभी 1s के साथ अधिकतम आकार के आयत बाइनरी सब-मैट्रिक्स को खोजने के लिए एक प्रोग्राम पर चर्चा करेंगे।
इसके लिए हमें 2D मैट्रिक्स प्रदान किया जाएगा जिसमें शून्य और एक होंगे। हमारा काम केवल वाले वाले सबसे बड़े 2D मैट्रिक्स सबसेट को खोजना है।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
#define R 4
#define C 4
//finding the maximum area
int maxHist(int row[]) {
stack<int> result;
int top_val;
int max_area = 0;
int area = 0;
int i = 0;
while (i < C) {
if (result.empty() || row[result.top()] <= row[i])
result.push(i++);
else {
top_val = row[result.top()];
result.pop();
area = top_val * i;
if (!result.empty())
area = top_val * (i - result.top() - 1);
max_area = max(area, max_area);
}
}
while (!result.empty()) {
top_val = row[result.top()];
result.pop();
area = top_val * i;
if (!result.empty())
area = top_val * (i - result.top() - 1);
max_area = max(area, max_area);
}
return max_area;
}
//returning area of largest required subset
int maxRectangle(int A[][C]) {
int result = maxHist(A[0]);
for (int i = 1; i < R; i++) {
for (int j = 0; j < C; j++)
if (A[i][j])
A[i][j] += A[i - 1][j];
result = max(result, maxHist(A[i]));
}
return result;
}
int main() {
int A[][C] = {
{ 0, 1, 1, 0 },{ 1, 1, 1, 1 },{ 1, 1, 1, 1 },{ 1, 1, 0, 0 },
};
cout << "Area of maximum rectangle is " <<
maxRectangle(A);
return 0;
} आउटपुट
Area of maximum rectangle is 8