在C ++中找到面积总和等于k的最大面积矩形子矩阵

假设我们有一个二维矩阵矩阵和一个值K,我们必须找到最长的矩形子矩阵,其总和与K相同。

所以,如果输入像

28-56
-778-3
11-1443
-43110

K = 9

那么输出将是左上点(1,0)和下右点(3,2)。

-778
11-144
-431

为了解决这个问题,我们将遵循以下步骤-

  • 最大:= 100

  • 定义一个函数sum_k(),它将使用一个数组arr,start,end,n,k,

  • 定义一张映射

  • 总和:= 0,最大长度:= 0

  • 对于初始化i:= 0,当i <n时,更新(将i增加1),执行-

    • 如果maximum_length <(i-map [sum-k]),则-

    • maximum_length:= i-map [sum-k]

    • 开始:= map [sum-k] + 1

    • 结束:=我

    • map [sum]:= i

    • 最大长度:= i + 1

    • 开始:= 0

    • 结束:=我

    • sum:= sum + arr [i]

    • 如果和等于k,则-

    • 如果总和不在映射中,则-

    • 如果(sum-k)在映射中,则-

    • 当maximum_length不为0时返回true

    • 从主要方法中,执行以下操作-

    • row:=垫子的行数,col:=垫子的列数

    • 定义大小为行的数组临时文件。

    • 定义一个数组final_point = {0,0,0,0}

    • maxArea:= -inf

    • 对于initial left:= 0,当left <col时,更新(将left增加1),执行-

      • 返回“未找到子矩阵”

      • 对于初始化i:= 0,当i <行,更新(将i增加1)时,执行-

      • sum:= sum_k(温度,上,下,行,k)

      • 区域:=(下-上+ 1)*(右-左+ 1)

      • 如果sum为非零且maxArea <area,则-

      • temp [i]:= temp [i] + mat [i,right]

      • final_point [0]:=向上,final_point [1]:=向下

      • final_point [2]:=左,final_point [3]:=右

      • maxArea:=面积

      • 用0填充温度

      • 对于初始化right:= left,当right <col时,更新(将right增加1),执行-

      • 如果final_point是[0,0,0,0]并且mat [0,0]不是k,则

      • 显示左上角的点(final_point [0],final_point [2])

      • 显示右下角的点(final_point [1],final_point [3])

      • 显示垫子元素。

      例 

      让我们看下面的实现以更好地理解-

      #include <bits/stdc++.h>
      using namespace std;
      const int MAX = 100;
      bool sum_k(int arr[], int& start, int& end, int n, int k) {
         unordered_map<int, int> map;
         int sum = 0, maximum_length = 0;
         for (int i = 0; i < n; i++) {
            sum += arr[i];
            if (sum == k) {
               maximum_length = i + 1;
               start = 0;
               end = i;
            }
            if (map.find(sum) == map.end())
               map[sum] = i;
            if (map.find(sum - k) != map.end()) {
               if (maximum_length < (i - map[sum - k])) {
                  maximum_length = i - map[sum - k];
                  start = map[sum - k] + 1;
                  end = i;
               }
            }
         }
         return (maximum_length != 0);
      }
      void sum_zero(vector<vector<int>> &mat, int k) {
         int row = mat.size();
         int col = mat[0].size();
         int temp[row], area;
         bool sum;
         int up, down;
         vector<int> final_point = {0,0,0,0};
         int maxArea = INT_MIN;
         for (int left = 0; left < col; left++) {
            memset(temp, 0, sizeof(temp));
            for (int right = left; right < col; right++) {
               for (int i = 0; i < row; i++)
                  temp[i] += mat[i][right];
               sum = sum_k(temp, up, down, row, k);
               area = (down - up + 1) * (right - left + 1);
               if (sum && maxArea < area) {
                  final_point[0] = up;
                  final_point[1] = down;
                  final_point[2] = left;
                  final_point[3] = right;
                  maxArea = area;
               }
            }
         }
         if (final_point[0] == 0 && final_point[1] == 0 && final_point[2] == 0 &&
         final_point[3] == 0 && mat[0][0] != k) {
            cout << "No sub-matrix found";
            return;
         }
         cout << "(Top, Left) Coordinate: " << "(" << final_point[0] << ", " << final_point[2] << ")" << endl;
         cout << "(Bottom, Right) Coordinate: " << "(" << final_point[1] << ", " << final_point[3] << ")" << endl;
         for (int j = final_point[0]; j <= final_point[1]; j++) {
            for (int i = final_point[2]; i <= final_point[3]; i++)
               cout << mat[j][i] << " ";
            cout << endl;
         }
      }
      main(){
         vector<vector<int>> v = {
            { 2, 8, -5, 6 },
            { -7, 7, 8, -3 },
            { 11, -14, 4, 3 },
            { -4, 3, 1, 10 }};
         sum_zero(v, 9);
      }

      输入项

      {{ 2, 8, -5, 6 },
      { -7, 7, 8, -3 },
      { 11, -14, 4, 3 },
      { -4, 3, 1, 10 }},
      9

      输出结果

      (Top, Left) Coordinate: (1, 0)
      (Bottom, Right) Coordinate: (3, 2)
      -7 7 8
      11 -14 4
      -4 3 1
      猜你喜欢