Ma trận con nhị phân hình chữ nhật có kích thước tối đa với tất cả các số 1 trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để tìm ma trận con nhị phân hình chữ nhật có kích thước tối đa với tất cả 1s.

Đối với điều này, chúng tôi sẽ được cung cấp ma trận 2D chứa các số 0 và các số một. Nhiệm vụ của chúng ta là tìm tập hợp con ma trận 2D lớn nhất chỉ chứa những cái duy nhất.

Ví dụ

#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;
}

Đầu ra

Area of maximum rectangle is 8