C++에서 모두 1인 최대 크기의 직사각형 이진 부분행렬

이 튜토리얼에서는 모두 1인 최대 크기의 직사각형 이진 부분행렬을 찾는 프로그램에 대해 논의할 것입니다.

이를 위해 0과 1을 포함하는 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