C++で行列内の合計が最大となる行を見つける方法

この問題では、N×N のサイズを持つ行列 mat[][] が与えられ、その中から要素の合計が最大となる行を見つけることが課題となります。

問題を理解するための例

入力

mat[][] = {
    8, 4, 1, 9
    3, 5, 7, 9
    2, 4, 6, 8
    1, 2, 3, 4
}

出力

Row 2, sum 24

説明

各行の合計を計算すると以下のようになります。

行1: 合計 = 8+4+1+9 = 22
行2: 合計 = 3+5+7+9 = 24
行3: 合計 = 2+4+6+8 = 20
行4: 合計 = 1+2+3+4 = 10

この中で最も合計が大きいのは行2（合計 24）であるため、これが答えとなります。

解法のアプローチ

この問題に対するシンプルな解決策は、各行の要素の合計を順番に計算し、その最大値を記録していくというものです。

具体的には、次の手順で処理を行います。

1. 現在の最大合計（maxSum）を初期化する。
2. 各行について、その行に含まれるすべての要素の合計を求める。
3. 計算した合計が現在の最大値より大きければ、最大値とその行のインデックスを更新する。
4. すべての行を走査し終えたら、最大の合計を持つ行を出力する。

解法の実装例

以下は、この解法の動作を示す C++ プログラムです。

#include <iostream>
using namespace std;
#define R 4
#define C 4

void findMax1Row(int mat[R][C]) {
    int maxSumRow = 0, maxSum = -1;
    int i, index;
    for (i = 0; i < R; i++) {
        int sum = 0;
        for(int j = 0; j < C; j++){
            sum += mat[i][j];
        }
        if(sum > maxSum){
            maxSum = sum;
            maxSumRow = i;
        }
    }
    cout<<"Row : "<<(maxSumRow+1)<<" has the maximum sum which is "<<maxSum;
}

int main() {
    int mat[R][C] = {
        {8, 4, 1, 9},
        {3, 5, 7, 9},
        {2, 4, 6, 8},
        {1, 2, 3, 4}
    };
    findMax1Row(mat);
    return 0;
}

出力

Row : 2 has the maximum sum which is 24

計算量について

このアルゴリズムは、行列のすべての要素を一度ずつ参照するため、時間計算量は O(N²) となります。ここで N は行列の行数（および列数）です。空間計算量は追加の配列などを必要としないため O(1) です。

このように、各行の合計を逐次的に比較していくだけで、効率的に合計が最大の行を特定することができます。