C++で合計がkに等しい最大面積の長方形の部分行列を見つけます

その場合、出力は左上のポイントが（1、0）、右下のポイントが（3、2）になります。

これを解決するには、次の手順に従います-

• MAX：=100

• 関数sum_k（）を定義します。これには、1つの配列arr、start、end、n、k、

  が必要です。

• 1つのマップを定義する

• 合計：=0、maximum_length：=0

• 初期化i：=0の場合、i

  • 合計：=合計+ arr [i]

  • 合計がkと同じ場合、-

    • maximum_length：=i + 1

    • start：=0

    • 終了：=i

  • 合計がマップにない場合、-

    • map [sum]：=i

  • （sum --k）がマップにある場合、-

    • maximum_length <（i --map [sum --k]）の場合、-

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

      • start：=map [sum --k] + 1

      • 終了：=i

• maximum_lengthが0でない場合はtrueを返します

• メインの方法から、次のようにします-

• 行：=マットの行数、列：=マットの列数

• サイズの配列温度を定義します：行。

• 配列を定義しますfinal_point={0,0,0,0}

• maxArea：=-inf

• 左初期化の場合：=0、左

  • 温度を0で埋める

  • 右初期化の場合：=左、右

    • 初期化i：=0の場合、i <行の場合、更新（iを1増やします）、実行-

      • temp [i]：=temp [i] + mat [i、right]

    • sum：=sum_k（temp、up、down、row、k）

    • エリア：=（下-上+ 1）*（右-左+ 1）

    • 合計がゼロ以外でmaxArea

      • final_point [0]：=up、final_point [1]：=down

      • final_point [2]：=左、final_point [3]：=右

      • maxArea：=area

  • 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