C++で増加部分列の最大積を求める方法を解説

本記事では、増加部分列の最大積(Maximum Product of Increasing Subsequence)を求めるアルゴリズムについて、C++での実装例とあわせて詳しく解説します。

問題概要

整数型の配列が与えられます。元の配列の順序を保ったまま任意の個数の要素を選んで部分列を作り、その要素が単調増加(増加部分列)になるとき、積の最大値を求めるのが目的です。

例えば、配列 {3, 100, 4, 5, 150, 6} の場合、増加部分列 {3, 100, 150} を選ぶと積は「3 × 100 × 150 = 45000」となり、これが最大値となります。

アプローチ:動的計画法(DP)

この問題は、最長増加部分列(LIS: Longest Increasing Subsequence)の考え方を応用して、動的計画法で効率よく解くことができます。

• mpis[i] を「i 番目の要素で終わる増加部分列の積の最大値」と定義します。
• 初期値は mpis[i] = arr[i](自分自身だけの部分列)とします。
• 各 i に対して、それより前方のすべての j を調べ、「arr[i] > arr[j]」かつ「mpis[i] < mpis[j] * arr[i]」を満たす場合に値を更新します。
• 最終的に mpis 配列全体の最大値が答えになります。

C++による実装例

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

// 増加部分列の最大積を返す関数
ll lis(ll arr[], ll n) {
    ll mpis[n];
    // 初期値の設定(自分自身のみの部分列)
    for (int i = 0; i < n; i++)
        mpis[i] = arr[i];

    // 動的計画法で各位置における最大積を更新
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j] && mpis[i] < (mpis[j] * arr[i]))
                mpis[i] = mpis[j] * arr[i];

    // 全体の最大値を返す
    return *max_element(mpis, mpis + n);
}

int main() {
    ll arr[] = { 3, 100, 4, 5, 150, 6 };
    ll n = sizeof(arr) / sizeof(arr[0]);
    printf("%lld", lis(arr, n));
    return 0;
}

出力

45000

コードの解説

このプログラムでは、まず各要素を「その要素だけで構成される部分列」とみなし、積の初期値を設定しています。その後、二重ループによって各要素 i について、より小さいインデックス j の要素との大小関係を確認し、積が大きくなる場合は値を更新していきます。

処理が完了すると、mpis 配列には「それぞれの要素で終わる増加部分列の最大積」が格納されているため、max_element で全体の最大値を取得すれば答えが得られます。

注意点と計算量

• オーバーフロー対策: 積は掛け合わせるたびに急激に大きくなるため、long long 型を使用してオーバーフローを防ぐことが重要です。
• 時間計算量: 二重ループを使用するため O(n²) です。
• 空間計算量: 補助配列 mpis に O(n) 必要です。

このように、LISの動的計画法の枠組みを「長さ」から「積」に置き換えるだけで、増加部分列の最大積問題をシンプルに解くことができます。