C++で最大和の交互部分列を求める方法｜動的計画法による解説

この問題では、n個の整数からなる配列 arr[] が与えられます。目的は、配列の最初の要素から始まる最大和の交互部分列を見つけるプログラムを作成することです。

交互部分列とは、要素が「減少 → 増加 → 減少」のように増減を交互に繰り返す部分列のことです。なお、この問題では逆順の交互部分列（最初に増加するパターン）は、最大和を求めるうえで有効な候補として扱いません。

それでは、具体例を使って問題を理解しましょう。

入力例

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

出力

27

説明

開始要素：5 → 減少：1 → 増加：6 → 減少：2 → 増加：4 → 以降選択不可
ここでは、4・8・9 を部分列の末尾の要素として利用できます。
和 = 5 + 1 + 6 + 2 + 4 + 9 = 27

解法のアプローチ

この問題は動的計画法（DP）を用いて解きます。具体的には、次の2つの配列を用意します。

• maxSumInc[i]：arr[i] で終わり、直前の要素より大きくなる（増加）交互部分列の最大和
• maxSumDec[i]：arr[i] で終わり、直前の要素より小さくなる（減少）交互部分列の最大和

配列を先頭から順に走査し、各要素が交互部分列の条件を満たすかどうかを確認しながら値を更新していきます。すべてのインデックスについて最大和を計算し、n個の要素を走査し終えた時点での最大値を返します。

実装例

以下は、この解法の動作を示すC++プログラムです。

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

int maxVal(int x, int y){
    if(x > y)
        return x;
    return y;
}

int calcMaxSumAltSubSeq(int arr[], int n) {
    int maxSum = -10000;
    int maxSumDec[n];
    bool isInc = false;
    memset(maxSumDec, 0, sizeof(maxSumDec));
    int maxSumInc[n];
    memset(maxSumInc, 0, sizeof(maxSumInc));
    maxSumDec[0] = maxSumInc[0] = arr[0];
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[i]) {
                maxSumDec[i] = maxVal(maxSumDec[i], maxSumInc[j] + arr[i]);
                isInc = true;
            }
            else if (arr[j] < arr[i] && isInc)
                maxSumInc[i] = maxVal(maxSumInc[i], maxSumDec[j] + arr[i]);
        }
    }
    for (int i = 0; i < n; i++)
        maxSum = maxVal(maxSum, maxVal(maxSumInc[i], maxSumDec[i]));
    return maxSum;
}

int main() {
    int arr[] = {8, 2, 3, 5, 7, 9, 10};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "先頭からの最大和交互部分列は " << calcMaxSumAltSubSeq(arr, n);
    return 0;
}

出力

先頭からの最大和交互部分列は 25

計算量の目安

• 時間計算量：O(n²) — 各要素について、それ以前のすべての要素との組み合わせを確認する必要があるため
• 空間計算量：O(n) — 増加・減少それぞれの最大和を保持する2つの配列が必要なため