C ++程序中最大大小为1的矩形二进制子矩阵

在这个问题中，我们得到一个n * m大小的二维矩阵bin [] []，其中包含在线二进制数，即0/1。我们的任务是创建一个程序，以找到全为1的最大尺寸矩形二进制子矩阵，并返回最大面积。

让我们举个例子来了解这个问题，

输入项

bin[][] = {
   {1, 0, 1, 1, 1}
   {0, 1, 1, 1, 1}
   {0, 0, 1, 1, 1}
   {1, 1, 1, 1, 1}
}

输出结果

12

说明

对于此矩形，面积最大。

1, 1, 1
1, 1, 1
1, 1, 1
1, 1, 1

解决方法

要解决该问题，我们需要找到仅由1组成的最大可能的矩形子矩阵。为此，我们需要找到最大面积，直到当前行由矩形构成为止。

直到当前行的面积将通过首先查找到该列中当前元素的连续行数来计算。我们将考虑具有相同或更大数量一次的元素，即，如果所有元素具有不同的数量，我们将考虑最小的元素。到目前为止面积最大的行将是结果

示例

该程序说明了我们解决方案的工作原理，

#include <bits/stdc++.h>
using namespace std;
#define R 4
#define C 5
int calcAreaTillRow(int row[]){
   stack<int> area1s;
   int tos;
   int maxArea = 0;
   int curArea = 0;
   int i = 0;
   while (i < C) {
      if (area1s.empty() || row[area1s.top()] <= row[i])
         area1s.push(i++);
      else {
         tos = row[area1s.top()];
         area1s.pop();
         curArea = tos * i;
         if (!area1s.empty())
            curArea = tos * (i − area1s.top() − 1);
         maxArea = max(curArea, maxArea);
      }
   }
   while (!area1s.empty()) {
      tos = row[area1s.top()];
      area1s.pop();
      curArea = tos * i;
      if (!area1s.empty())
         curArea = tos * (i − area1s.top() − 1);
      maxArea = max(curArea, maxArea);
   }
   return maxArea;
}
int calcmaxRecSubMat1(int bin[][C]){
   int result = calcAreaTillRow(bin[0]);
   for (int i = 1; i < R; i++) {
      for (int j = 0; j < C; j++)
      if (bin[i][j])
         bin[i][j] += bin[i − 1][j];
      result = max(result, calcAreaTillRow(bin[i]));
   }
   return result;
}
int main(){
   int bin[][C] = {
      {1, 0, 1, 1, 1},
      {0, 1, 1, 1, 1},
      {0, 0, 1, 1, 1},
      {1, 1, 1, 1, 1}
   };
   cout<<"The area of maximum size rectangle binary sub−matrix with all 1s is "<<calcmaxRecSubMat1(bin);
   return 0;
}

输出结果

The area of maximum size rectangle binary sub-matrix with all 1s is 12