C++でn個の配列から昇順に選んだ要素の最大合計を求めるプログラム

この問題では、サイズ n×m の2次元行列が与えられます。私たちのタスクは、n 個の配列（行）から昇順となるように要素を選び、その合計の最大値を求めるプログラムを作成することです。

問題の概要

各行から1つずつ要素を選び、i 行目で選んだ要素が (i+1) 行目で選んだ要素より小さくなるようにします。この条件を満たす選び方の中で、合計が最大になるものを求めます。条件を満たす組み合わせが存在しない場合は、解が存在しないことを示す -1 を返します。

入力例と出力例

入力

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

出力

31

解説

最大合計となる要素の選び方：
6 + 7 + 8 + 10 = 31

・1行目から 6 を選択（この行の最大値）
・2行目から 7 を選択（最大値の12を選ぶと解が成立しないため）
・3行目から 8 を選択（最大値の13を選ぶと解が成立しないため）
・4行目から 10 を選択（この行の最大値）

解法のアプローチ

この問題を解く一つの方法は、最後の配列（最終行）から要素を選ぶことから始め、上の行へ向かって「直前に選んだ要素より小さい最大の要素」を選んでいくというものです。

この方法では、ある i 行目に「(i+1) 行目で選んだ要素より小さい値が存在しない」というケースが発生する可能性があります。その場合は -1 を返して解なしとします。

また、あらかじめ各行を昇順にソートしておくと、計算効率が大きく向上します。昇順にソートしておけば最大値はインデックス m−1 の位置にあり、左に進むほど値が小さくなるため、条件を満たす最大の要素を簡単に見つけられるからです。

アルゴリズム

maxSum = 0、currMax を初期化します。

ステップ1：

各行の配列を昇順にソートする。

ステップ2：

currMax = mat[n−1][m−1]（最終行の最大値）とし、
maxSum = currMax として更新する。

ステップ3：

i = n−2 から 0 まで、行を下から上へループします。

ステップ3.1：

mat[i][] 内で currMax より小さい最大の要素を
インデックス j で見つける。

ステップ3.2：

j < 0 となった場合（該当する値が見つからない場合）、
-1 を返す。

ステップ3.3：

currMax を更新する：currMax = mat[i][j]。

ステップ3.4：

maxSum を更新する：maxSum += currMax。

ステップ4：

maxSum を返す。

C++実装例

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

#include <bits/stdc++.h>
#define M 5
using namespace std;
int calcMaxSumMat(int mat[][M], int n) {
    for (int i = 0; i < n; i++)
        sort(mat[i], mat[i] + M);
    int maxSum = mat[n − 1][M − 1];
    int currMax = mat[n − 1][M − 1];
    int j;
    for (int i = n − 2; i >= 0; i−−) {
        for (j = M − 1; j >= 0; j−−) {
            if (mat[i][j] < currMax) {
                currMax = mat[i][j];
                maxSum += currMax;
                break;
            }
        }
        if (j == −1)
            return 0;
    }
    return maxSum;
}
int main() {
    int mat[][M] = {
        {4, 5, 1, 3, 6},
        {5, 9, 2, 7, 12},
        {12, 1, 3, 6, 8},
        {10, 5, 7, 2, 4}
    };
    int n = sizeof(mat) / sizeof(mat[0]);
    cout<<"n個の配列から昇順に選んだ要素の最大合計は "<<calcMaxSumMat(mat, n);
    return 0;
}

出力結果

n個の配列から昇順に選んだ要素の最大合計は 31

まとめ

このアルゴリズムは、下の行から順に条件を満たす最大の要素を選んでいく貪欲法的なアプローチです。事前のソートにより探索が単純化され、時間計算量は O(n·m·log m)（ソート部分）＋ O(n·m)（探索部分）となります。条件を満たす選び方が存在しない場合には -1 を返すことで、解の有無も正しく判定できます。