最大和増加部分列問題を解くための動的計画法アルゴリズム

この記事では、与えられた数列の中で、増加する順に並んだ部分列の合計の最大値を求める問題について解説します。この問題は、動的計画法を用いて効率的に解くことができます。

最大和増加部分列（MSIS）とは？

与えられた数列から、要素が昇順に並んでいる部分列を選びます。この部分列に含まれる要素の合計が最大になるものを、最大和増加部分列（Maximum Sum Increasing Subsequence; MSIS）と呼びます。

たとえば、数列 {1, 101, 2, 3, 100, 4, 5} が与えられた場合、MSIS は {1, 2, 3, 100} であり、その合計は 106 になります。

動的計画法によるアプローチ

この問題を解くために、動的計画法（Dynamic Programming; DP）のアプローチを用います。DP は、問題をより小さな部分問題に分割し、それらの解を再利用することで、効率的に問題を解決する手法です。

アルゴリズム

1. 初期化: 長さ n の入力配列 arr[] が与えられたとき、同じ長さの配列 msis[] を作成します。msis[i] は、arr[i] で終わる増加部分列の最大合計を格納します。初期状態では、各 msis[i] を arr[i] で初期化します。これは、各要素自体が長さ 1 の増加部分列であるためです。

2. 反復処理: 配列 arr[] を先頭から順に走査します（i = 1 から n-1）。各要素 arr[i] について、その前のすべての要素 arr[j]（j = 0 から i-1）を調べます。

   • もし arr[i] > arr[j] であれば、arr[i] を arr[j] で終わる増加部分列に追加することで、より大きな合計が得られる可能性があります。具体的には、msis[i] < msis[j] + arr[i] である場合、msis[i] を msis[j] + arr[i] で更新します。

3. 最大値の選択: msis[] 配列全体を走査し、その中の最大値を見つけます。この最大値が、最大和増加部分列の合計となります。

コード例（C++）

#include <iostream>
using namespace std;

int maxSumIS(int arr[], int n) {
    int i, j, max_sum = 0;
    int msis[n];

    // Initialize msis values for all indexes
    for (i = 0; i < n; i++)
        msis[i] = arr[i];

    // Compute maximum sum values in bottom up manner
    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];
        }
    }

    // Pick maximum of all msis values
    for (i = 0; i < n; i++) {
        if (max_sum < msis[i])
            max_sum = msis[i];
    }

    return max_sum;
}

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;
}

このコードは、配列を受け取り、動的計画法を用いてMSISの合計を計算します。

時間計算量と空間計算量

このアルゴリズムの時間計算量は O(n^2) です。これは、ネストされたループを使用して配列を反復処理するためです。空間計算量は O(n) で、msis[] 配列を格納するために使用されます。

まとめ

最大和増加部分列問題を動的計画法で解く方法について見てきました。この手法は、効率的であり、同様の最適化問題にも応用できます。

データ構造とアルゴリズムに関するより詳しい情報については、GeeksforGeeks を参照してください。