C++で行列内の要素ペアの最大差を効率的に求める方法

ここでは、整数値を持つ n × n の行列 mat が与えられた場合を考えます。すべてのインデックスの組み合わせの中から、mat(c, d) - mat(a, b) の最大値を見つけることが目的です。ただし、条件として c > a かつ d > b を満たす必要があります。

例えば、次のような行列があったとしましょう。

この場合の出力は 18 となります。mat[4][2] - mat[1][0] = 10 - (-8) の組み合わせが最大の差を生むためです。

解法のアプローチ

この問題を効率的に解くためには、事前に行列を前処理しておきます。具体的には、各インデックス (i, j) に対して、そこから右下の (n-1, n-1) までの範囲に含まれる要素の最大値を格納した補助配列を作成します。前処理の過程で、これまでに見つかった最大の差分も同時に更新していき、最終的にその最大値を返します。

この手法により、全組み合わせを総当たりで調べる O(n⁴) の計算量を、O(n²) まで削減できます。

サンプルコード

#include<iostream>
#define N 5
using namespace std;
int findMaxValue(int matrix[][N]) {
    int maxValue = -99999;
    int arr_max[N][N];
    arr_max[N-1][N-1] = matrix[N-1][N-1];
    int max_val = matrix[N-1][N-1];
    for (int j = N - 2; j >= 0; j--) {
        if (matrix[N-1][j] > max_val)
        max_val = matrix[N - 1][j];
        arr_max[N-1][j] = max_val;
    }
    max_val = matrix[N - 1][N - 1];
    for (int i = N - 2; i >= 0; i--) {
        if (matrix[i][N - 1] > max_val)
        max_val = matrix[i][N - 1];
        arr_max[i][N - 1] = max_val;
    }
    for (int i = N-2; i >= 0; i--) {
        for (int j = N-2; j >= 0; j--) {
            if (arr_max[i+1][j+1] - matrix[i][j] > maxValue)
            maxValue = arr_max[i + 1][j + 1] - matrix[i][j];
            arr_max[i][j] = max(matrix[i][j],max(arr_max[i][j + 1],arr_max[i + 1][j]) );
        }
    }
    return maxValue;
}
int main() {
    int mat[N][N] = {
        { 1, 2, -1, -4, -20 },
        { -8, -3, 4, 2, 1 },
        { 3, 8, 6, 1, 3 },
        { -4, -1, 1, 7, -6 },
        { 0, -4, 10, -5, 1 }
    };
    cout << "Maximum Value is " << findMaxValue(mat);
}

実行結果

Maximum Value is 18