【C++】動的計画法で解く最大和増加部分列（MSIS）｜DP-14の実装方法を徹底解説

はじめに

この記事では、動的計画法（Dynamic Programming：DP）を活用して「最大和増加部分列（Maximum Sum Increasing Subsequence：MSIS）」を求めるC++プログラムについて詳しく解説します。

この問題では、N個の整数を含む配列が与えられます。私たちのタスクは、配列の中から要素を選び出し、その合計値を最大化することです。ただし、選んだ要素は元の配列内での並び順を保ちながら、厳密に増加している（昇順に並んでいる）必要があります。

問題のポイント

「増加部分列」とは、元の配列の相対的な順序を崩さずに取り出した要素の列であり、かつ各要素が直前の要素よりも大きくなっているものを指します。目的は、そのような部分列の中で「要素の合計」が最大となるものを見つけることです。

なお、この問題は有名な「最長増加部分列（LIS）」の応用問題です。LISが部分列の長さを最大化するのに対し、MSISは部分列の合計値を最大化する点が異なります。

アルゴリズムの考え方

この問題は動的計画法を用いることで効率的に解くことができます。基本的な手順は以下の通りです。

1. 配列 msis[i] を「arr[i] を末尾とする増加部分列の合計の最大値」として定義します。
2. 初期化として、各要素に対し msis[i] = arr[i] と設定します（各要素が単独で部分列を構成する場合の値です）。
3. 各インデックス i について、それ以前のすべてのインデックス j（j < i）を走査します。もし arr[i] > arr[j] かつ msis[i] < msis[j] + arr[i] が成り立つならば、msis[i] を msis[j] + arr[i] に更新します。
4. 最終的に、msis 配列内の最大値が答えとなります。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
// 最大合計を返す関数
int maxSumIS(int arr[], int n) {
   int i, j, max = 0;
   int msis[n];
   // 各要素を初期値として設定
   for ( i = 0; i < n; i++ )
      msis[i] = arr[i];
   // 動的計画法で各位置の最大合計を更新
   for ( i = 1; i < n; i++ )
      for ( j = 0; j < i; j++ )
         if (arr[i] > arr[j] &&
            msis[i] < msis[j] + arr[i])
            msis[i] = msis[j] + arr[i];
    // 全体の最大値を求める
      for ( i = 0; i < n; i++ )
         if ( max < msis[i] )
            max = msis[i];
         return max;
}
int main() {
   int arr[] = {1, 101, 2, 3, 100, 4, 5};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Sum of maximum sum increasing subsequence is "<<
   maxSumIS( arr, n ) << endl;
   return 0;
}

実行結果

Sum of maximum sum increasing subsequence is 106

実行結果の解説

入力配列 {1, 101, 2, 3, 100, 4, 5} の場合、最大の合計を持つ増加部分列は {1, 2, 3, 100} であり、その合計は 1 + 2 + 3 + 100 = 106 となります。

一見すると {1, 101} のように大きな要素を選べば合計が大きくなりそうですが、101 を選んでしまうと後続の小さい要素（2, 3, 100）を組み合わせられなくなります。このように「局所的に大きな値を選ぶこと」と「全体の合計を最大化すること」は必ずしも一致しないため、動的計画法による全体的な探索が有効です。

計算量

• 時間計算量： O(n²) ― 各要素 i に対して、それ以前のすべての要素 j を比較するため二重ループが必要です。
• 空間計算量： O(n) ― 部分問題の解を保存するための補助配列 msis が必要です。

まとめ

最大和増加部分列の問題は、最長増加部分列（LIS）と同じ枠組みの動的計画法で解くことができます。dp配列に「その要素で終わる増加部分列の最大合計」を記録し、逐次更新していくのがポイントです。競技プログラミングやコーディング面接でも頻出のテーマなので、ぜひ実装をマスターしておきましょう。