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

問題概要

2次元行列 mat と値 K が与えられたとき、要素の合計がちょうど K に等しくなる長方形の部分行列のうち、面積が最大のものを見つけることを考えます。

たとえば、入力が以下の行列であったとします。

ここで K = 9 とした場合、出力は「左上の座標が (1, 0)」「右下の座標が (3, 2)」となります。実際に該当する部分行列は次の通りです。

この部分行列の合計を確認してみましょう。(-7 + 7 + 8) + (11 - 14 + 4) + (-4 + 3 + 1) = 8 + 1 + 0 = 9 となり、確かに K と一致しています。

アプローチのポイント

この問題は、累積和 と ハッシュマップ を組み合わせることで効率的に解けます。基本的な発想は、まず列のペア (left, right) をすべて列挙し、その2列に挟まれた各行の要素の和を配列 temp に蓄積していくことで、2次元の問題を1次元の「合計が K になる最長連続部分配列」の問題へと帰着させるというものです。

1次元配列において「合計が k になる最長の連続部分配列」を求める際は、ハッシュマップに各累積和が最初に現れたインデックスを記録しておきます。位置 i での累積和を sum とするとき、過去に累積和 sum − k がインデックス j で現れていれば、区間 [j+1, i] の合計はちょうど k になります。この性質により、線形時間で最長区間を特定できます。

アルゴリズム

具体的には、以下の手順に従います。

• MAX := 100 と定義します。
• 関数 sum_k() を定義します。この関数は、配列 arr、start、end、n、k を引数に取ります。
• マップを1つ定義します。
• sum := 0、maximum_length := 0 と初期化します。
• i := 0 から開始し、i < n の間 i を1ずつ増やしながら以下を繰り返します。
  • sum := sum + arr[i]
  • sum が k と等しい場合は、次のように設定します。
    • maximum_length := i + 1
    • start := 0
    • end := i
  • sum がまだマップに存在しない場合は、map[sum] := i と登録します。
  • (sum − k) がマップに存在する場合は、さらに次を判定します。
    • maximum_length < (i − map[sum − k]) である場合、次のように更新します。
      • maximum_length := i − map[sum − k]
      • start := map[sum − k] + 1
      • end := i
• maximum_length が 0 でなければ true を返します。

main 関数での処理

• row := mat の行数、col := mat の列数 とします。
• サイズ row の配列 temp を定義します。
• 配列 final_point = {0,0,0,0} を定義します。
• maxArea := −∞ と初期化します。
• left := 0 から開始し、left < col の間 left を1ずつ増やしながら以下を繰り返します。
  • temp を 0 で埋めます。
  • right := left から開始し、right < col の間 right を1ずつ増やしながら以下を繰り返します。
    • i := 0 から開始し、i < row の間 i を1ずつ増やしながら、temp[i] := temp[i] + mat[i][right] を実行します。
    • sum := sum_k(temp, up, down, row, k) を呼び出します。
    • area := (down − up + 1) × (right − left + 1) を計算します。
    • sum が非ゼロ かつ maxArea < area である場合は、次のように更新します。
      • final_point[0] := up、final_point[1] := down
      • final_point[2] := left、final_point[3] := right
      • maxArea := area
• final_point が [0,0,0,0] のまま かつ mat[0][0] ≠ k である場合は、「該当する部分行列は見つかりませんでした」と出力して終了します。
• 左上の点 (final_point[0], final_point[2]) を表示します。
• 右下の点 (final_point[1], final_point[3]) を表示します。
• 該当する部分行列の要素を表示します。

実装例

それでは、実際のC++による実装を見てみましょう。

#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

計算量

外側の2重ループで列のペアを O(col²) 通り試し、それぞれについて sum_k() がハッシュマップを用いて O(row) 時間で動作するため、全体の時間計算量は O(col² × row) となります。空間計算量は、一時配列とハッシュマップの分が必要で、O(row) です。