C++でn個の配列から昇順要素を選んで最大合計を求める方法

このチュートリアルでは、n個の配列から「昇順」という条件を満たすように要素を1つずつ選び、その合計を最大化するプログラムについて解説します。

ここでは、サイズMの配列がN個与えられます。各配列から1つずつ要素を選び、「前の配列から選んだ要素よりも、次の配列から選ぶ要素の方が大きい」という条件を満たしながら、合計の最大値を求めることが課題です。

アルゴリズムの考え方

この問題は、貪欲法（グリーディ法）を用いることで効率的に解くことができます。手順は以下の通りです。

1. まず、すべての配列をそれぞれ昇順にソートします。
2. 最後の配列の最大要素（末尾の要素）を出発点とし、これを合計の初期値とします。
3. 後ろの配列から前の配列へ向かって処理を進めます。各配列については末尾側から探索し、「直前に選んだ要素より小さい要素」の中で最も大きいものを選びます。
4. ある配列で条件を満たす要素が1つも存在しない場合は、有効な選び方が存在しないため0を返します。

後ろから処理を進めることで、各ステップで「条件を満たす中でできるだけ大きな値」を選択でき、結果的に全体の合計が最大化されます。

実装例

#include <bits/stdc++.h>
#define M 4
using namespace std;
//1つの要素を選んで最大合計を計算する
int maximumSum(int a[][M], int n) {
    for (int i = 0; i < n; i++)
        sort(a[i], a[i] + M);
    int sum = a[n - 1][M - 1];
    int prev = a[n - 1][M - 1];
    int i, j;
    for (i = n - 2; i >= 0; i--) {
        for (j = M - 1; j >= 0; j--) {
            if (a[i][j] < prev) {
                prev = a[i][j];
                sum += prev;
                break;
            }
        }
        if (j == -1)
            return 0;
    }
    return sum;
}
int main() {
    int arr[][M] = {
        {1, 7, 3, 4},
        {4, 2, 5, 1},
        {9, 5, 1, 8}
    };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maximumSum(arr, n);
return 0;
}

出力

18

動作の解説

上記の入力例では、各配列をソートすると {1, 3, 4, 7}、{1, 2, 4, 5}、{1, 5, 8, 9} となります。

• 最後の配列から最大値「9」を選択します。
• 2番目の配列から「9より小さい最大値」である「5」を選択します。
• 1番目の配列から「5より小さい最大値」である「4」を選択します。

したがって、合計は 9 + 5 + 4 = 18 となります。

計算量

ソートに各配列あたりO(M log M)かかるため、全体の時間計算量はO(N × M log M)です。その後の要素選択はO(N × M)で完了します。空間計算量はO(1)で、入力配列をそのまま利用するため追加メモリは不要です。