C++で行列の任意の列から最大の差を持つペアを検索する方法

N×N の行列が与えられたとき、行列の任意の列から要素のペアを取り出し、その差が最大になるペアを見つける問題を考えてみましょう。

例えば、次のような行列があるとします。

この場合、出力は 8 になります。最大の差を持つペアは 0 列目の (1, 9) だからです。

解法のアイデア

考え方は非常にシンプルです。各列ごとに最大値と最小値を求め、その差を計算します。そして、すべての列の中で最も大きな差を返せばよいのです。

アルゴリズムの手順

1. 各列について、最初の行の値を最大値・最小値の初期値として設定します。
2. 残りの行を順に走査しながら、最大値と最小値を更新していきます。
3. その列の最大値と最小値の差を計算し、これまでの最大の差と比較して大きい方を採用します。
4. すべての列の処理が完了したら、最大の差を結果として返します。

実装例(C++)

#include<iostream>
#define N 5
using namespace std;
int maxVal(int x, int y){
    return (x > y) ? x : y;
}
int minVal(int x, int y){
    return (x > y) ? y : x;
}
int colMaxDiff(int mat[N][N]) {
    int diff = INT_MIN;
    for (int i = 0; i < N; i++) {
        int max_val = mat[0][i], min_val = mat[0][i];
        for (int j = 1; j < N; j++) {
            max_val = maxVal(max_val, mat[j][i]);
            min_val = minVal(min_val, mat[j][i]);
        }
        diff = maxVal(diff, max_val - min_val);
    }
    return diff;
}
int main() {
    int mat[N][N] = {{ 1, 2, 3, 4, 5 }, { 5, 3, 5, 4, 0 }, { 5, 6, 7, 8, 9 }, { 0, 6, 3, 4, 12 },
{ 9, 7, 12, 4, 3 }};
    cout << "Max difference : " << colMaxDiff(mat) << endl;
}

出力

Max difference : 12

計算量の分析

このアルゴリズムの時間計算量は O(N²) です。行列のすべての要素をちょうど 1 回ずつ走査するためです。また、追加のデータ構造を使用しないため、空間計算量は O(1) となり、非常に効率的な解法といえます。

なお、差が最大になるペアは必ずしも隣接する要素である必要はなく、同じ列内の任意の 2 つの要素でよい点に注意してください。そのため、各列の最大値と最小値さえわかれば、その差がその列で達成可能な最大の差となります。