C++で解説：プレフィックス内の増加部分列の最大和の求め方（プレフィックス後の指定要素を必ず含む）

この問題では、N個の整数からなる配列 arr[] と、2つのインデックス x・y が与えられます。求めるのは「インデックス x までのプレフィックスから選んだ増加部分列の最大和」であり、プレフィックスより後ろにあるインデックス y の要素を必ず部分列に含める必要があります。

問題の概要

インデックス x までの範囲で増加部分列の最大和を求め、そのうえでインデックス y の要素を必ず含めます。

具体例で問題を確認しましょう。

入力

arr[] = {1, 5, 9, 131, 6, 100, 11, 215}, x = 4, y = 6

出力

26

説明

インデックス 3 までの部分列を選び、最後に arr[6] = 11 を含めます。

このとき部分列は {1, 5, 9, 11} となり、その和は 1+5+9+11 = 26 です。

解法アプローチ

1. シンプルな解法

まずインデックス x までの要素で新しい配列を作成し、その末尾にインデックス y の要素を追加します。続いてすべての増加部分列を計算し、arr[y] を含められないものを除外しながら最大和（maxSum）を求めます。ただし、この方法は組み合わせの数が膨大になりやすく、非効率です。

2. 動的計画法（DP）による解法

より効率的なのが動的計画法の活用です。2次元配列 DP[][] を用意し、増加部分列の最大和を格納していきます。DP[x][y] の値が「インデックス x までの範囲で arr[y] を含む増加部分列の最大和」に対応します。

実装例

この解法の動作を示すプログラムです。

#include <iostream>
using namespace std;
int DP[100][100];
void preCalcMaxSum(int arr[], int N){
    for (int i = 0; i < N; i++) {
        if (arr[i] > arr[0])
            DP[0][i] = arr[i] + arr[0];
        else
            DP[0][i] = arr[i];
    }
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[j] > arr[i] && j > i) {
                if (DP[i - 1][i] + arr[j] > DP[i - 1][j])
                    DP[i][j] = DP[i - 1][i] + arr[j];
                else
                    DP[i][j] = DP[i - 1][j];
            }
            else
                DP[i][j] = DP[i - 1][j];
        }
    }
}
int main() {
    int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
    int N = sizeof(arr) / sizeof(arr[0]);
    int x = 4, y = 6;
    preCalcMaxSum(arr, N);
    cout<<"The maximum sum increasing subsequence from a prefix and a given element after prefix is must is ";
    cout<<DP[x][y];
    return 0;
}

出力

The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26

より効率的な解法

さらに効率を高めるには、「インデックス x までの範囲で、部分列の最大要素が arr[y] より小さくなるような増加部分列の最大和」を求める方法が有効です。ここでも動的計画法を利用します。この条件を満たす最大和を先に計算しておけば、最後に arr[y] を加えるだけで答えが得られます。

実装例

この解法の動作を示すプログラムです。

#include <iostream>
using namespace std;
int calcMaxSum(int arr[], int n, int x, int y){
    int DP[x] = {0};
    int maxSum = -1;
    for (int i = 0; i <= x; i++)
        DP[i] = arr[i];
    for (int i = 0; i <= x; i++) {
        if (arr[i] >= arr[y]) {
            continue;
        }
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j])
                DP[i] += arr[j];
                maxSum = max(maxSum, DP[i]);
        }
    }
    if (maxSum == -1) {
        return arr[y];
    }
    return maxSum + arr[y];
}
int main(){
    int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
    int N = sizeof(arr) / sizeof(arr[0]);
    int x = 4, y = 6;
    cout<<"The maximum sum increasing subsequence from a prefix and a given element after prefix is must is ";
    cout<<calcMaxSum(arr, N, x, y);
    return 0;
}

出力

The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26

このように、動的計画法を用いることで、プレフィックス内の増加部分列の最大和を効率的に計算し、指定した要素 arr[y] を必ず含む解を求めることができます。全列挙による素朴なアプローチと比べ、計算量を大幅に抑えられる点が大きなメリットです。