【C++】行列内の隣接する4つの要素の最大積を求める方法

このチュートリアルでは、行列内の隣接する4つの要素の積の最大値を求めるC++プログラムについて解説します。

対象となるのは正方行列です。私たちのタスクは、縦・横・斜めのいずれかの方向に隣接する4つの要素を選び、その積が最大になる組み合わせを見つけることです。

アルゴリズムの考え方

基本的なアプローチは以下の通りです。

• 行列のすべての要素を順番に走査します。
• 各要素を起点として、「横方向」「縦方向」「右下がりの斜め方向」「左下がりの斜め方向」の4パターンについて、連続する4つの要素の積を計算します。
• 配列の範囲外を参照しないよう、インデックスの境界条件を確認した上で計算を行います。
• 計算した積が現在の最大値よりも大きければ、最大値を更新します。

各マスに対して行う処理は定数回であるため、このアルゴリズム全体の計算量はO(n²)となり、非常に効率的です。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
const int n = 5;

// 最大積を求める関数
int FindMaxProduct(int arr[][n], int n) {
    int max = 0, result;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 横方向のチェック
            if ((j - 3) >= 0) {
                result = arr[i][j] * arr[i][j - 1] * arr[i][j - 2] * arr[i][j - 3];
                if (max < result)
                    max = result;
            }
            // 縦方向のチェック
            if ((i - 3) >= 0) {
                result = arr[i][j] * arr[i - 1][j] * arr[i - 2][j] * arr[i - 3][j];
                if (max < result)
                    max = result;
            }
            // 斜め方向(対角線)のチェック
            if ((i - 3) >= 0 && (j - 3) >= 0) {
                result = arr[i][j] * arr[i - 1][j - 1] * arr[i - 2][j - 2] * arr[i - 3][j - 3];
                if (max < result)
                    max = result;
            }
            // 逆斜め方向(反対角線)のチェック
            if ((i - 3) >= 0 && (j - 1) <= 0) {
                result = arr[i][j] * arr[i - 1][j + 1] * arr[i - 2][j + 2] * arr[i - 3][j + 3];
                if (max < result)
                    max = result;
            }
        }
    }
    return max;
}

int main() {
    int arr[][5] = {
        {1, 2, 3, 4, 5},
        {6, 7, 8, 9, 1},
        {2, 3, 4, 5, 6},
        {7, 8, 9, 1, 0},
        {9, 6, 4, 2, 3}
    };
    cout << FindMaxProduct(arr, n);
    return 0;
}

出力

3024

実行結果の解説

この例では、2行目に「6, 7, 8, 9」という横方向に隣接して並んだ4つの要素があり、その積は 6 × 7 × 8 × 9 = 3024 となります。他のどの方向・位置の組み合わせよりも大きな積となるため、これが最大値として出力されます。

なお、この実装では最大値の初期値を0としているため、扱う行列の要素が非負の整数であることを前提としています。負の値を含む行列に対応する場合は、初期値を最小整数値に設定するなどの工夫が必要です。