C++で最大和ビトニック部分列を求める方法【動的計画法で解説】

この問題では、整数の配列 arr[] が与えられ、C++ を使って「最大和ビトニック部分列(Maximum Sum Bitonic Subsequence)」を求めるプログラムを作成します。

ビトニック部分列(Bi-tonic subsequence)とは、要素がまず増加し続け、途中から減少に転じるという特性を持つ特別な部分列のことです。

問題を理解するための例

入力

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

出力

33

説明

合計が最大となるビトニック部分列は {2, 3, 7, 9, 6, 5, 1} です。

合計 = 2 + 3 + 7 + 9 + 6 + 5 + 1 = 33

解法のアプローチ

最大和ビトニック部分列を効率よく求めるために、incSeq[] と decSeq[] という2つの補助配列を用意します。

• incSeq[i]: インデックス i を終点とする、arr[0...i] の範囲で厳密に増加する部分列の最大合計
• decSeq[i]: インデックス i を始点とする、arr[i...n-1] の範囲で厳密に減少する部分列の最大合計

すべての計算が終わったら、(incSeq[i] + decSeq[i] - arr[i]) の最大値を maxSum として返します。arr[i] を引く理由は、ビトニック列の頂点となる要素 arr[i] が incSeq と decSeq の両方に含まれ、二重に加算されてしまうためです。

このアルゴリズムの計算量は O(N²)、必要な追加メモリは O(N) です。

実装例

上記の解法を示すプログラムは以下のとおりです。

#include <iostream>
using namespace std;
int calcMaxVal(int a, int b){
    if(a > b)
        return a;
    return b;
}
int findMaxSumBiTonicSubSeq(int arr[], int N){
    int maxSum = -1;
    int incSeq[N], decSeq[N];
    for (int i = 0; i < N; i++){
        decSeq[i] = arr[i];
        incSeq[i] = arr[i];
    }
    for (int i = 1; i < N; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j] && incSeq[i] < incSeq[j] + arr[i]) incSeq[i] = incSeq[j] + arr[i];
    for (int i = N - 2; i >= 0; i--)
        for (int j = N - 1; j > i; j--)
            if (arr[i] > arr[j] && decSeq[i] < decSeq[j] + arr[i])
            decSeq[i] = decSeq[j] + arr[i];
    for (int i = 0; i < N; i++)
        maxSum = calcMaxVal(maxSum, (decSeq[i] + incSeq[i] - arr[i]));
    return maxSum;
}
int main(){
    int arr[] = {4, 2, 3, 7, 9, 6, 3, 5, 1};
    int N = sizeof(arr) / sizeof(arr[0]);
    cout<<"The Maximum Sum of Bi-tonic subsequence is : "<<findMaxSumBiTonicSubSeq(arr, N);
    return 0;
}

出力

The Maximum Sum of Bi-tonic subsequence is : 33