C++で解く「最大和減少部分列」問題 ― 動的計画法による実装方法を徹底解説

はじめに

本記事では、N個の整数からなる配列 arr[] が与えられたとき、その中から厳密に減少する部分列を抜き出し、要素の合計が最大になる値（最大和減少部分列）をC++で求める方法を解説します。

問題の概要

配列の中から要素を選び、選んだ順序が左から右へ単調減少となるように部分列を作ります。そのとき、部分列の要素の合計として考えられる最大値を求めるのが目的です。

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

入力例

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

出力例

17

解説

この場合、合計が最大となる減少部分列は {10, 5, 2} です。10 + 5 + 2 = 17 が答えとなります。

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

この問題は動的計画法を使うことで効率的に解くことができます。基本的な考え方は以下の通りです。

• maxSum[i] を「インデックス i の要素を末尾とする減少部分列の合計の最大値」と定義します。
• 初期値として maxSum[i] = arr[i] とします（自分自身のみの部分列）。
• i より前の各要素 j について、arr[i] < arr[j]（減少関係が成り立つ）かつ maxSum[j] + arr[i] が現在の maxSum[i] より大きければ更新します。

これを式で表すと次のようになります。

maxSum[i] = arr[i] + max(maxSum[0 … i-1])（ただし arr[j] > arr[i] を満たす j のみ）

最終的な答えは、配列 maxSum[] の中の最大値です。

計算量は二重ループを使用するため O(N²)、必要な記憶領域は O(N) となります。

C++での実装例

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

#include <iostream>
using namespace std;

int findMaxSumDecSubSeq(int arr[], int N){
    int maximumSum = 0;
    int maxSum[N];

    // 初期化：各要素自身が部分列の先頭になりうる
    for (int i = 0; i < N; i++)
        maxSum[i] = arr[i];

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

    // 最大値を求める
    for (int i = 0; i < N; i++)
        if (maximumSum < maxSum[i])
            maximumSum = maxSum[i];

    return maximumSum;
}

int main(){
    int arr[] = { 5, 4, 100, 3, 2, 101, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << "最大和減少部分列の合計: " << findMaxSumDecSubSeq(arr, N);
    return 0;
}

実行結果

最大和減少部分列の合計: 106

処理の流れのポイント

1. 初期化： maxSum[] を配列 arr[] の各要素で初期化します。これは「その要素だけからなる長さ1の部分列」を意味します。
2. 遷移： 各インデックス i に対し、それより前のすべての j を調べ、arr[j] > arr[i] であれば maxSum[j] に arr[i] を加えた値で更新できるかチェックします。
3. 答えの抽出： すべての maxSum[i] の中で最も大きい値が、求める最大和となります。

上記の例では、100 → 3 → 2 → 1 という減少部分列の合計 106 が最大となることが確認できます。

まとめ

最大和減少部分列の問題は、最長増加部分列（LIS）と同じ発想で解ける典型的な動的計画法の応用問題です。maxSum 配列を用いて「各位置を末尾とする部分列の最大和」を順に更新していくことで、O(N²) の時間計算量で確実に答えを求められます。競技プログラミングやアルゴリズム学習の基礎として、ぜひ理解しておきましょう。