最大和増加部分列とは？動的計画法による求め方とC++実装例を解説

最大和増加部分列（Maximum Sum Increasing Subsequence）とは、与えられた整数列の中から選んだ部分列のうち、すべての要素が増加順に並んでおり、かつ総和が最大となるもののことです。

この問題は動的計画法（DP）を用いて解くのが一般的です。基本の考え方は、「配列の各位置 i に対して、arr[i] で終わる最大和増加部分列を記録しておく」というものです。i より手前にある各 j について「arr[j] < arr[i] であり、その時点で総和が最大となる部分列」を選び、その末尾に arr[i] を付け足すことで、L[i] を順次構築していきます。

入力と出力

入力：整数列 {3, 2, 6, 4, 5, 1}
出力：総和が最大となる増加部分列 {3, 4, 5}

この例では {3, 6}（総和 9）や {2, 4, 5}（総和 11）なども増加部分列ですが、{3, 4, 5} の総和 12 が最大であるため、これが答えになります。

アルゴリズム

maxSumSubSeq(array, n)

入力：数値の列 array、要素数 n
出力：総和が最大となる増加部分列

Begin
    大きさ n の「配列の配列」subSeqLen を用意する
    subSeqLen[0] に arr[0] を追加する

    for i = 1 to n-1 do
        for j = 0 to i-1 do
            if arr[i] > arr[j] かつ subSeqLen[i] の総和 < subSeqLen[j] の総和 then
                subSeqLen[i] := subSeqLen[j]
            end if
        end for
        // 部分列は必ず arr[i] で終わる
        subSeqLen[i] に arr[i] を追加する
    end for

    res := subSeqLen[0]

    subSeqLen のすべての要素について
        if subSeqLen[i] の総和 > res の総和 then
            res := subSeqLen[i]
        end if
    end for

    res の内容を出力する
End

計算量

要素同士を二重ループで比較するため、時間計算量は O(n²) です。サンプルコードでは比較のたびに findAllSum() で総和を再計算していますが、subSeqLen[i] の総和をあらかじめ別の配列にキャッシュしておけば、さらに高速化できます。

C++による実装例

#include <iostream>
#include <vector>
using namespace std;

// ベクトル内の全要素の総和を求める
int findAllSum(vector<int> arr) {
    int sum = 0;
    for (int i = 0; i < arr.size(); i++) {
        sum += arr[i];
    }
    return sum;
}

void maxSumSubSeq(int arr[], int n) {
    // arr[i] で終わる最大和増加部分列を格納する
    vector<vector<int> > subSeqLen(n);
    subSeqLen[0].push_back(arr[0]);

    for (int i = 1; i < n; i++) {          // インデックス 1 以降を順に処理
        for (int j = 0; j < i; j++) {      // すべての j（j < i）を確認
            if ((arr[i] > arr[j]) &&
                (findAllSum(subSeqLen[i]) < findAllSum(subSeqLen[j]))) {
                subSeqLen[i] = subSeqLen[j];   // 総和が大きい候補で置き換え
            }
        }
        subSeqLen[i].push_back(arr[i]);    // 部分列の末尾に arr[i] を追加
    }

    // 総和が最大となる部分列を探索
    vector<int> res = subSeqLen[0];
    for (int i = 0; i < subSeqLen.size(); i++) {
        if (findAllSum(subSeqLen[i]) > findAllSum(res)) {
            res = subSeqLen[i];
        }
    }

    // 結果の出力
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = { 3, 2, 6, 4, 5, 1 };
    int n = 6;
    cout << "最大和部分列: ";
    maxSumSubSeq(arr, n);
    return 0;
}

実行結果

最大和部分列: 3 4 5

このように、各位置で終わる最良の部分列を順次構築していくことで、列全体の最大和増加部分列を求められます。最長増加部分列（LIS）と同じ動的計画法の枠組みで解ける応用問題なので、DPの理解を深める演習題材としてもおすすめです。