C++を使って行列内の合計が最大となるペアを求める方法

この記事では、与えられた行列（2次元配列）の中から、合計が最大となる2つの要素のペアを見つける方法について詳しく解説します。

入力 : matrix[m][n] = {
    { 3, 5, 2 },
    { 2, 6, 47 },
    { 1, 64, 66 } }

出力 : 130
説明 : 要素64と66のペアによる最大合計は130です。

入力 : matrix[m][n] = {
    { 55, 22, 46 },
    { 6, 2, 1 },
    { 3, 24, 52 } }

出力 : 107
説明 : 要素55と52のペアによる最大合計は107です。

解決策へのアプローチ

ここからは、この問題を解くための複数の手法について、わかりやすく順を追って説明していきます。

全探索（ブルートフォース）アプローチ

まず考えられるのは単純な全探索です。MAX変数を最初の2要素の合計値で初期化し、配列全体を走査しながらすべてのペアの合計を計算し、その値が現在のMAXより大きければ更新していきます。しかし、この方法では時間計算量がO((m×n)²)となり、大規模な行列に対しては非常に多くの時間を要してしまいます。

効率的なアプローチ

より効率的なのが、MAX1とMAX2という2つの変数を使う方法です。まず両変数をINT_MINで初期化し、2次元配列を一度だけ走査します。走査中、現在の要素がMAX1より大きければ、MAX2にMAX1の値を代入し、MAX1に現在の要素を代入します。こうすることで、行列内で最も大きい2つの数値が見つかり、それらの合計が必然的に最大の合計となります。この方法なら時間計算量はO(m×n)で済みます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

int main() {
    int m = 3, n = 3;
    // 値で行列を初期化
    int matrix[m][n] = {
        { 55, 22, 46 },
        { 6, 2, 1 },
        { 3, 24, 52 }
    };

    // 最大の2つの数を保持するためMAX1とMAX2を初期化
    int MAX1 = INT_MIN;
    int MAX2 = INT_MIN;
    int result;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 現在の要素がMAX1より大きいかどうかを判定
            if (matrix[i][j] > MAX1) {
                MAX2 = MAX1;
                MAX1 = matrix[i][j];
            }
            // 現在の要素がMAX1とMAX2の間にあるかどうかを判定
            else if (matrix[i][j] > MAX2 && matrix[i][j] <= MAX1) {
                MAX2 = matrix[i][j];
            }
        }
    }
    // 2つの最大値を加算して最大合計を求める
    result = MAX1 + MAX2;
    cout << "行列内の最大合計 : " << result;

    return 0;
}

出力

行列内の最大合計 : 107

コードの解説

• 2次元配列に要素を格納し、MAX1とMAX2をINT型の最小値（INT_MIN）で初期化します。
• 行列全体を走査します。
  • 現在の要素がMAX1より大きい場合、MAX2にMAX1の値を代入し、MAX1に現在の要素を代入します。
  • 現在の要素がMAX1以下でMAX2より大きい場合、MAX2に現在の要素を代入します。
• 走査終了後、MAX1とMAX2を加算して結果を算出し、出力します。

まとめ

この記事では、与えられた行列の中から合計が最大となるペアを見つける方法について解説しました。問題を解くための2つのアプローチを比較紹介し、あわせてC++での実装コードも取り上げました。同じロジックはJava、C、Pythonなど他のプログラミング言語でも簡単に実装できます。本記事が皆さんのお役に立てば幸いです。