C++で行列の各行から選んだ要素の合計を最大化する方法

この記事では、2次元行列 mat[][] が与えられたとき、C++を使って各行から条件を満たす要素を1つずつ選び、その合計を最大化するプログラムの作成方法を解説します。

問題の概要

行列の各行から1つずつ要素を選んで合計を求めます。ただし、現在の行で選ぶ要素は、直前の行で選んだ要素よりも大きい値でなければなりません。この条件を満たす要素の組み合わせの中で、合計が最大になるものを求め、条件を満たす選び方が存在しない場合は -1 を出力します。

具体例で問題を確認してみましょう。

入力

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

出力

22

説明

1行目 = 6
2行目 = 7
3行目 = 9
合計 = 6 + 7 + 9 = 22

解法のアプローチ

最もシンプルな解法は、行列の最終行から順に処理を進めることです。まず最終行で最大の数値を見つけて MaxSum に加算し、その後1行上へ移動して、「下の行で選んだ最大値よりも小さい数値」の中で最大のものを探します。この操作を最上行に到達するまで繰り返します。途中で条件を満たす数値が見つからなかった場合は、-1 を返します。

この手法の計算量は O(行数 × 列数) であり、行列全体を一度走査するだけで答えが得られるため、効率的な解法といえます。

実装例

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

#include <iostream>
using namespace std;
#define row 3
#define col 3

int RowMaxSum(int a[row][col]){
    int maxValLastRow = 10000;
    int maxSum = 0;
    for (int i = row - 1; i >= 0; i--){
        int maxNo = -1;
        for (int j = 0; j < col; j++)
            if (maxValLastRow > a[i][j] && a[i][j] > maxNo)
                maxNo = a[i][j];
        if (maxNo == -1)
            return -1;
        maxValLastRow = maxNo;
        maxSum += maxValLastRow;
    }
    return maxSum;
}
int main(){
    int a[3][3] = {{4, 6, 1},
                   {2, 5, 7},
                   {9, 1, 2}};
    cout<<"The maximum sum of elements from each row in the matrix is "<<RowMaxSum(a);
    return 0;
}

実行結果

The maximum sum of elements from each row in the matrix is 22

まとめ

本記事では、行列の下の行から順に「直前の行で選んだ値より小さい最大値」を貪欲法（グリーディ法）的に選んでいくことで、各行から1要素ずつ取り出した合計の最大値を求める方法を紹介しました。条件を満たせない場合は -1 を返すことで、解が存在しないケースにも対応できます。