C++で増加部分列の最大積を求める方法【動的計画法で解説】

本記事では、サイズnの整数型配列arr[]が与えられたとき、「増加部分列（Increasing Subsequence）」の中で要素の積が最大となる値を求める問題を、C++を使ってわかりやすく解説します。

問題の概要

配列内の要素から任意の長さの増加部分列を選び、その積の最大値を求めることが目的です。増加部分列とは、元の配列の順序を保ちながら、各要素が直前の要素よりも大きくなるような部分列のことを指します。

入出力例

入力

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

出力

2160

解説

考えられる増加部分列：
{5, 6, 8, 9} → 積 = 2160
{5, 6, 7, 9} → 積 = 1890

この例では、{5, 6, 8, 9}を選んだ場合の積「2160」が最大となります。

解法のアプローチ

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

• prod[i] を「i番目の要素で終わる増加部分列の最大積」として定義する。
• 初期状態では、prod[i] の値を arr[i] 自身に設定する（自分1つだけの部分列の場合）。
• 各要素iについて、それ以前のすべての要素jを調べ、arr[i] > arr[j] かつ prod[j] * arr[i] > prod[i] を満たす場合に prod[i] を更新する。
• 最後に、prod配列の中から最大値を答えとして返す。

アルゴリズム

初期化：

prod[] を arr[] の各要素で初期化
maxProd = -1000

ステップ1：

i を 0 から n-1 までループ

ステップ1.1：

j を 0 から i までループ

ステップ1.1.1：

もし arr[i] > arr[j] かつ arr[i] * prod[j] > prod[i] ならば
    prod[i] = prod[j] * arr[i]

ステップ2：

prod[] の中から最大値 maxProd を見つける

ステップ3：

maxProd を返す

C++での実装例

#include <iostream>
using namespace std;

long calcMaxProdSubSeq(long arr[], int n) {
    long maxProdSubSeq[n];
    for (int i = 0; i < n; i++)
        maxProdSubSeq[i] = arr[i];

    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j] && maxProdSubSeq[i] < (maxProdSubSeq[j] * arr[i]))
                maxProdSubSeq[i] = maxProdSubSeq[j] * arr[i];

    long maxProd = -1000;
    for (int i = 0; i < n; i++) {
        if (maxProd < maxProdSubSeq[i])
            maxProd = maxProdSubSeq[i];
    }
    return maxProd;
}

int main() {
    long arr[] = {5, 4, 6, 8, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "増加部分列の最大積は " << calcMaxProdSubSeq(arr, n);
    return 0;
}

実行結果

増加部分列の最大積は 2160

計算量について

この解法の時間計算量はO(n²)、空間計算量はO(n)です。二重ループで各要素の組み合わせを比較するため、配列サイズが大きくなると処理時間が増加しますが、すべての部分列を網羅的に列挙する方法と比べれば、はるかに効率的なアプローチです。

まとめ

増加部分列の最大積を求める問題は、最長増加部分列（LIS）の応用問題の一つです。「その要素で終わる増加部分列の最大積」をdpテーブルに記録しながら更新していくことで、効率的に解答を得られます。ぜひ実際にコードを書いて、動作を確認してみてください。