C++で長さm以下となる最大合計部分配列を求めるアルゴリズム

この問題では、長さの異なる n 個の配列が与えられます。求めるのは、合計長さが m 以下となるように各配列から部分配列を選択し、その要素の合計を最大化することです。

つまり、複数の配列の中から部分配列を取り出し、それら全体の合計値を最大化しながら、選んだ部分配列の長さの総和を m 以内に収める必要があります。

問題例

具体的な入力と出力を見て、問題を理解しましょう。

入力

n = 3, m = 4
arrOfArr[][] = {
    {5, 2, -1, 4, -3},
    {3, -2, 1, 6},
    {-2, 0, 5}
}

出力

20

解説

選択した部分配列：{5, 4}, {6}, {5}
合計長さ = 2 + 1 + 1 = 4
合計値 = 5 + 4 + 6 + 5 = 20

この例では、1番目の配列から「5」と「4」、2番目の配列から「6」、3番目の配列から「5」を選ぶことで、長さ4以内で合計20という最大値が得られます。

解決アプローチ：動的計画法（DP）

この問題は動的計画法（Dynamic Programming）を用いて効率的に解くことができます。基本的な考え方は次の通りです。

まず DP テーブルを作成し、長さ k（0 から m まで）ごとの累積和を計算します。各配列について、「0 から m までの各長さに対して達成できる最大合計値」を二次元の DP テーブルに保存していきます。すべての配列を処理し終えた後、DP テーブルの最終行に格納されている最大値が答えとなります。

アルゴリズムの手順

1. 各配列について累積和（prefix sum）を計算します。
2. 累積和を利用して、その配列内で長さ j の部分配列の最大合計を求めます。
3. DP テーブルを更新し、前の配列までの結果と現在の配列の結果を組み合わせます。
4. すべての配列を処理後、DP テーブルの最終行から最大値を取得します。

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
#define N 5
int findMax(int a, int b){
    if(a > b)
        return a;
        return b;
}
int findMaxSumArray(int arr[][N], int M) {
    int DP[N][M];
    int sumArray[M];
    int sum[M];
    memset(DP, -1, sizeof(DP[0][0]) * N * M);
    sumArray[0] = 0;
    DP[0][0] = 0;
    for (int i = 1; i <= 5; i++) {
        int len = arr[i - 1][0];
        for (int j = 1; j <= len; j++) {
            sumArray[j] = arr[i - 1][j];
            sumArray[j] += sumArray[j - 1];
            sum[j] = -100;
        }
        for (int j = 1; j <= len && j <= 6; j++)
            for (int k = 1; k <= len; k++)
                if (j + k - 1 <= len)
                    sum[j] = findMax(sum[j], sumArray[j + k - 1] - sumArray[k - 1]);
        for (int j = 0; j <= 6; j++)
            DP[i][j] = DP[i - 1][j];
        for (int j = 1; j <= 6; j++)
            for (int cur = 1; cur <= j && cur <= len; cur++)
                DP[i][j] = findMax(DP[i][j], DP[i - 1][j - cur] + sum[cur]);
    }
    int maxSum = 0;
    for (int i = 0; i <= 6; i++)
        maxSum = findMax(maxSum, DP[5][i]);
        return maxSum;
}
int main() {
    int arr[][N] = { { 3, 2, -1, 6 },
                     { 2, 7, -1 },
                     { 3, 2, 2, -4 } };
    int m = 4;
    cout<<"Maximum sum array of length less than or equal to "<<m<<" : "<<findMaxSumArray(arr, m);
}

実行結果

Maximum sum array of length less than or equal to 4 : 15

このプログラムでは、最初の要素に各配列の長さを格納した形式でデータを与えています。実行すると、合計長さが4以下の条件における最大合計値「15」が出力されます。

まとめ

本記事では、複数の配列から合計長さ m 以下となる最大合計部分配列を求める問題について解説しました。動的計画法を用いることで、各配列の部分配列の候補を体系的に評価し、最適な組み合わせを効率的に導き出すことができます。累積和と DP テーブルを組み合わせたこの手法は、類似したナップサック型の最適化問題にも応用可能です。