अधिकतम उप-मैट्रिक्स क्षेत्र जिसमें सी ++ में 0 की गिनती से 1 की संख्या एक से अधिक है

इस ट्यूटोरियल में, हम अधिकतम उप-मैट्रिक्स क्षेत्र को खोजने के लिए एक कार्यक्रम पर चर्चा करेंगे, जिसमें 0 की गिनती से 1 की एक से अधिक की गिनती होगी।

इसके लिए हमें 0 और 1 वाले मैट्रिक्स के साथ प्रदान किया जाएगा। हमारा कार्य अधिकतम क्षेत्र का उप-मैट्रिक्स प्राप्त करना है जिसमें 0 से अधिक 1 है

उदाहरण

#include <bits/stdc++.h>
using namespace std;
#define SIZE 10
//finding length of longest sub-matrix
int lenOfLongSubarr(int arr[],
int n, int& start, int& finish) {
   unordered_map<int, int> um;
   int sum = 0, maxLen = 0;
   for (int i = 0; i < n; i++) {
      sum += arr[i];
      if (sum == 1) {
         start = 0;
         finish = i;
         maxLen = i + 1;
      }
      else if (um.find(sum) == um.end()) um[sum] = i;
      if (um.find(sum - 1) != um.end()) {
         if (maxLen < (i - um[sum - 1])) start = um[sum - 1] + 1;
         finish = i;
         maxLen = i - um[sum - 1];
      }
   }
   return maxLen;
}
//finding the maximum area
void largestSubmatrix(int mat[SIZE][SIZE], int n) {
   int finalLeft, finalRight, finalTop, finalBottom;
   int temp[n], maxArea = 0, len, start, finish;
   for (int left = 0; left < n; left++) {
      memset(temp, 0, sizeof(temp));
      for (int right = left; right < n; right++) {
         for (int i = 0; i < n; ++i)
         temp[i] += mat[i][right] == 0 ? -1 : 1;
         len = lenOfLongSubarr(temp, n, start, finish);
         if ((len != 0) && (maxArea < (finish - start + 1) * (right - left + 1))) {
            finalLeft = left;
            finalRight = right;
            finalTop = start;
            finalBottom = finish;
            maxArea = (finish - start + 1) * (right - left + 1);
         }
      }
   }
   cout << "(Top, Left): (" << finalTop << ", " << finalLeft << ")\n";
   cout << "(Bottom, Right): (" << finalBottom << ", " << finalRight << ")\n";
   cout << "Maximum area: " << maxArea;
}
int main() {
   int mat[SIZE][SIZE] = {
      { 1, 0, 0, 1 },
      { 0, 1, 1, 1 },
      { 1, 0, 0, 0 },
      { 0, 1, 0, 1 }
   };
   int n = 4; largestSubmatrix(mat, n);
   return 0;
}

आउटपुट

(Top, Left): (1, 1)
(Bottom, Right): (3, 3)
Maximum area: 9