【C++】動的計画法（DP）で最大合計増加部分列を求める方法

本記事では、サイズ n の配列 arr[] が与えられたとき、動的計画法（Dynamic Programming：DP）を用いて「最大合計増加部分列（Maximum Sum Increasing Subsequence）」を求めるC++プログラムを解説します。

問題の概要

最大合計増加部分列とは、各要素が直前の要素より大きいという条件を満たす部分列（Subsequence）の中で、要素の合計が最大となるものを指します。つまり、単調に増加しながら、かつ合計値が最も大きくなるような部分列を見つけることが目的です。

具体例で問題を理解しよう

入力

arr[] = {4, 2, 3, 6, 5, 9}

出力

20

解説

合計が最大となる増加部分列は以下の通りです。
{2, 3, 6, 9} = 2 + 3 + 6 + 9 = 20

なお、{4, 6, 9} のような部分列も増加部分列ですが、その合計は19であり、{2, 3, 6, 9} の20より小さくなります。

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

この問題は動的計画法を使うことで効率的に解くことができます。

基本的な考え方：

• sumDP[i] を「i番目の要素を必ず含む増加部分列の合計の最大値」と定義します。
• 初期状態として、sumDP[i] = arr[i]（自分自身のみの部分列）と設定します。
• i より前の各要素 j について、「arr[j] < arr[i]」かつ「sumDP[j] + arr[i] > sumDP[i]」を満たす場合、sumDP[i] を更新します。
• 最終的に sumDP 配列内の最大値が答えとなります。

この手法の計算量は時間 O(n²)、空間 O(n) です。

C++実装例

以下は、上記のアルゴリズムを実装したプログラムです。

#include <iostream>
using namespace std;

// 2つの値のうち大きい方を返す補助関数
int retMaxVal(int x, int y){
    if(x > y)
        return x;
    return y;
}

int calcMaxSubSeqSum(int arr[], int n) {
    int maxSum = 0;
    int sumDP[n];

    // 初期化：各位置の合計を自身の値で初期化
    for (int i = 0; i < n; i++)
        sumDP[i] = arr[i];

    // 動的計画法による更新処理
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if ( (sumDP[i] < (sumDP[j] + arr[i])) && (arr[i] > arr[j]) )
                sumDP[i] = sumDP[j] + arr[i];

    // DP配列の中から最大値を取得
    for (int i = 0; i < n; i++)
        maxSum = retMaxVal(sumDP[i], maxSum);

    return maxSum;
}

int main() {
    int arr[] = {4, 2, 3, 6, 5, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"動的計画法による最大合計増加部分列の合計値： "
        <<calcMaxSubSeqSum(arr, n);
    return 0;
}

実行結果

動的計画法による最大合計増加部分列の合計値： 20

まとめ

最大合計増加部分列の問題は、最長増加部分列（LIS）の応用問題と言えます。各位置での最大合計を記録するDP配列を用いることで、すべての増加部分列を実際に列挙することなく、効率よく答えを求めることができます。ぜひ本記事のコードを参考に、動的計画法の考え方をマスターしてください。