C++プログラムで指定サイズの最大合計を持つ正方形部分行列を出力する方法

N×N の行列が与えられたとき、M ≤ N かつ M ≥ 1 を満たすサイズ M×M の部分行列の中から、すべての要素の合計が最大となるものを見つけます。入力される行列には、0・正の整数・負の整数のいずれも含まれる可能性があります。

例

入力:
    {{1, 1, 1, 1, 1},
    {2, 2, 2, 2, 2},
    {3, 3, 3, 3, 3},
    {4, 4, 4, 4, 4},
    {5, 5, 5, 5, 5}}
出力:
    4 4
    5 5

単純なアプローチとその課題

最も直感的な解法は、元の N×N 行列から取り出せるすべての M×M 部分行列について合計を計算し、その中で最大のものを出力する方法です。このアプローチは理解しやすい反面、時間計算量が O(N² × M²) となるため、行列が大きくなると非効率になります。

そこで本記事では、「スライディングウィンドウ(累積和)」の考え方を利用することで、計算量を O(N²) まで削減できる効率的な手法を紹介します。

アルゴリズム

基本的な流れは次のとおりです。

1. まず各列ごとに縦方向へスライディングウィンドウを適用し、「連続する k 行分の合計」を補助配列に前計算します。
2. 次に、その補助配列の各行に対して横方向へ再度スライディングウィンドウを適用し、k×k ブロックの合計の最大値とその位置を求めます。
3. 最後に、記録しておいた位置を起点として k×k の要素を出力します。

開始
ステップ1 → 関数 void matrix(int arr[][size], int k) を宣言
    もし k > size ならば
        処理を中断して戻る
    補助配列 int array[size][size] を宣言
    各列 j(0 ≤ j < size)について:
        sum = 0 で初期化
        i = 0 から k 未満まで sum += arr[i][j](先頭 k 行の縦方向の合計)
        array[0][j] = sum を設定
        i = 1 から size-k+1 未満まで:
            sum += (arr[i+k-1][j] − arr[i-1][j])(縦方向のスライディングウィンドウ)
            array[i][j] = sum を設定
    maxsum = INT_MIN、*pos = NULL で初期化
    各行 i(0 ≤ i < size-k+1)について:
        sum = 0 で初期化
        j = 0 から k 未満まで sum += array[i][j](先頭 k 列の横方向の合計)
        もし sum > maxsum ならば
            maxsum = sum、pos = &(arr[i][0]) を更新
        j = 1 から size-k+1 未満まで:
            sum += (array[i][j+k-1] − array[i][j-1])(横方向のスライディングウィンドウ)
            もし sum > maxsum ならば
                maxsum = sum、pos = &(arr[i][j]) を更新
    pos を起点として k 行 × k 列の要素を順に出力
ステップ2 → main() 内で
    int array[size][size] を {{1,1,1,1,1},{2,2,2,2,2},{3,3,3,3,3},{4,4,4,4,4},{5,5,5,5,5}} で宣言
    int k = 2 を宣言
    matrix(array, k) を呼び出す
停止

C++による実装例

#include <bits/stdc++.h>
using namespace std;
#define size 5
void matrix(int arr[][size], int k){
    if (k > size) return;
    int array[size][size];
    for (int j=0; j<size; j++){
        int sum = 0;
        for (int i=0; i<k; i++)
            sum += arr[i][j];
        array[0][j] = sum;
        for (int i=1; i<size-k+1; i++){
            sum += (arr[i+k-1][j] - arr[i-1][j]);
            array[i][j] = sum;
        }
    }
    int maxsum = INT_MIN, *pos = NULL;
    for (int i=0; i<size-k+1; i++){
        int sum = 0;
        for (int j = 0; j<k; j++)
            sum += array[i][j];
        if (sum > maxsum){
            maxsum = sum;
            pos = &(arr[i][0]);
        }
        for (int j=1; j<size-k+1; j++){
            sum += (array[i][j+k-1] - array[i][j-1]);
            if (sum > maxsum){
                maxsum = sum;
                pos = &(arr[i][j]);
            }
        }
    }
    for (int i=0; i<k; i++){
        for (int j=0; j<k; j++)
            cout << *(pos + i*size + j) << " ";
        cout << endl;
    }
}
int main(){
    int array[size][size] = {
        {1, 1, 1, 1, 1},
        {2, 2, 2, 2, 2},
        {3, 3, 3, 3, 3},
        {4, 4, 4, 4, 4},
        {5, 5, 5, 5, 5},
    };
    int k = 2;
    matrix(array, k);
    return 0;
}

実行結果

上記のプログラムを実行すると、次の出力が得られます。

4 4
5 5

この結果は、元の行列の左下に位置する 2×2 の部分行列 {{4, 4}, {5, 5}} が、合計値 18 で最大であることを示しています。全探索方式では O(N² × M²) かかる計算が、スライディングウィンドウを用いることで O(N²) に抑えられる点が、この手法の大きな利点です。