C++で2次元配列における最小合計部分行列を求めるアルゴリズム

問題概要

整数要素で構成される2次元配列(行列)が与えられたとき、その中から部分行列を取り出し、合計が最小となる値を求めるのが本記事のテーマです。

それでは、具体的な入出力シナリオを見ていきましょう。

入出力例1

入力 −

int matrix[size][size] = { {2, 3, -1, 5}, {-2, 9, -1, 6}, {5, 6, 9, -9}, {-6, 1, 1, 1} }

出力 − 与えられた2次元配列における最小合計部分行列は: -9

説明 − 4行4列(サイズ4x4)の2次元配列が与えられています。この中から合計が最小となる部分行列を探すと、答えは -9 になります。

入出力例2

入力 −

int matrix[row][column] = { {4, 1, 3}, {-1, -1, -1}, {6, 2, 3} }

出力 − 与えられた2次元配列における最小合計部分行列は: -3

説明 − 3行3列(サイズ3x3)の2次元配列が与えられています。2行目全体を選んだ「1行3列」の部分行列により、最小合計 -3 が達成されます。

プログラムで使用するアプローチ

• 整数型の2次元配列を入力として受け取り、処理用の関数 Minimum_Matrix(matrix) にデータを渡します。

• 関数 Minimum_Matrix(matrix) の内部では以下を行います。

  • 一時変数として int result = INT_MAX、int arr[row]、int total、int first、int end を宣言します。

  • 外側のループで temp を0から column 未満まで回し、ループ内で配列要素をすべて0に初期化します。続いて temp_2 を temp から column 未満まで回す二重ループを構築し、その内部で i を0から row 未満まで回しながら arr[i] = arr[i] + matrix[i][temp_2] として各行の累積和を計算します。

  • total に関数 Algo_Kad(arr, &first, &end, row) の戻り値を代入します。

  • total が result より小さい場合、result を total で更新します。

  • 最終的な result を出力します。

• 関数 int Algo_Kad(int* arr, int* first, int* end, int max_size)(カダネのアルゴリズム)の内部では以下を行います。

  • 一時変数として int total = 0、int result = INT_MAX、int temp = 0、そして *end = -1 を宣言します。

  • ループで i を0から max_size 未満まで回し、total = total + arr[i] と累積していきます。

  • total が0より大きい場合は total を0に、temp を i + 1 にリセットします。

  • そうでない場合(total が result より小さい場合)、result を total に、*first を temp に、*end を i に更新します。

  • *end が -1 と等しくなければ、result を返します。

  • すべて正の値だったケースに備え、result を arr[0] に、*first を0に、*end を0に設定します。

  • ループで i を1から max_size 未満まで回し、arr[i] が result より小さければ result、*first、*end をそれぞれ更新します。

  • result を返します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
#define row 4
#define column 4
int Algo_Kad(int* arr, int* first, int* end, int max_size)
{
    int total = 0;
    int result = INT_MAX;
    int temp = 0;
    *end = -1;
    for(int i = 0; i < max_size; ++i)
    {
        total = total + arr[i];
        if(total > 0)
        {
            total = 0;
            temp = i + 1;
        }
        else if(total < result)
        {
            result = total;
            *first = temp;
            *end = i;
        }
    }
    if(*end != -1)
    {
        return result;
    }
    result = arr[0];
    *first = 0;
    *end = 0;

    for(int i = 1; i < max_size; i++)
    {
        if(arr[i] < result)
        {
            result = arr[i];
            *first = i;
            *end = i;
        }
    }
    return result;
}
void Minimum_Matrix(int matrix[][column])
{
    int result = INT_MAX;
    int arr[row];
    int total;
    int first;
    int end;

    for(int temp = 0; temp < column; ++temp)
    {
        memset(arr, 0, sizeof(arr));
        for(int temp_2 = temp; temp_2 < column; ++temp_2)
        {
            for(int i = 0; i < row; ++i)
            {
                arr[i] = arr[i] + matrix[i][temp_2];
            }

            total = Algo_Kad(arr, &first, &end, row);

            if(total < result)
            {
                result = total;
            }
        }
    }
    cout<<"Minimum sum submatrix in a given 2D array is: "<<result;
}
int main()
{
    int matrix[row][column] = {{2, 3, -1, 5},
                               {-2, 9, -1, 6},
                               { 5, 6, 9, -9},
                               { -6, 1, 1, 1} };
    Minimum_Matrix(matrix);
    return 0;
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

Minimum sum submatrix in a given 2D array is: -9