C++を使って行列内で合計が最大の列を見つける方法

ここでは、サイズ M × N の行列が与えられたときに、要素の合計が最大となる列を見つける方法を解説します。

この問題では、難しいアルゴリズムを用いる必要はありません。行列を列方向に走査して各列の合計値を計算し、その合計が最大であれば、合計値と該当する列のインデックスを出力するというシンプルなアプローチで十分です。

アルゴリズムの手順

処理の流れは以下の通りです。

1. 最大合計値を格納する変数 maxSum を INT_MIN で初期化し、列のインデックスを格納する index を -1 に設定します。
2. 各列（0 ～ N-1）について、colSum 関数を使ってその列の要素の合計を計算します。
3. 計算した合計が maxSum より大きければ、maxSum と index を更新します。
4. すべての列を走査し終えたら、最大の合計値とその列のインデックスを出力します。

サンプルコード

#include<iostream>
#define M 5
#define N 5
using namespace std;
int colSum(int colIndex, int mat[M][N]){
   int sum = 0;
   for(int i = 0; i<M; i++){
      sum += mat[i][colIndex];
   }
   return sum;
}
void maxColumnSum(int mat[M][N]) {
   int index = -1;
   int maxSum = INT_MIN;
   for (int i = 0; i < N; i++) {
      int sum = colSum(i, mat);
      if (sum > maxSum) {
         maxSum = sum;
         index = i;
      }
   }
   cout << "Index: " << index << ", Column Sum: " << maxSum;
}
int main() {
   int mat[M][N] = {
      { 1, 2, 3, 4, 5 },
      { 5, 3, 1, 4, 2 },
      { 5, 6, 7, 8, 9 },
      { 0, 6, 3, 4, 12 },
      { 9, 7, 12, 4, 3 },
   };
   maxColumnSum(mat);
}

実行結果

Index: 4, Column Sum: 31

この例では、5 行 5 列の行列の中で最も合計が大きいのはインデックス 4 の列（0 番目から数えて 5 列目）であり、その合計値は 31 となります。各列の合計はそれぞれ「20」「24」「26」「24」「31」であり、この中で最大となるのが最後の列です。

計算量について

このプログラムの時間計算量は O(M × N) です。すべての列について各行の要素を一度ずつ参照するためです。また、追加のメモリは定数個の変数のみを使用するため、空間計算量は O(1) となります。