C++でサイズ3の増加部分列の最大積を求める方法【効率的なアルゴリズム解説】

問題の概要

この問題では、n個の正の整数からなる配列 arr[] が与えられます。求めるのは、サイズ3の増加部分列における最大の積です。

具体的には、以下の条件を満たす3つの要素の組み合わせのうち、積が最大になるものを見つける必要があります。

arr[i] * arr[j] * arr[k] が最大
arr[i] < arr[j] < arr[k] かつ i < j < k

つまり、値が増加しており、かつインデックスの順序も増加している3つの要素を選ぶ必要があります。

入出力例

入力:

arr = {5, 9, 2, 11, 4, 7}

出力:

495

説明:

条件を満たすサイズ3の部分列は以下の通りです
(5, 9, 11) → 積 = 5×9×11 = 495
(2, 4, 7) → 積 = 2×4×7 = 56
最大値 = 495

解法1: 総当たり法（ブルートフォース）

最もシンプルな解法は、配列を3重ループで走査し、条件を満たすすべての3要素の組み合わせを列挙する方法です。各組み合わせの積を計算し、その中で最大のものを返します。

アルゴリズム

初期化:

maxProd = -1000

ステップ1:

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

ステップ1.1:

j を i+1 から n-2 までループ

ステップ1.1.1:

if (arr[i] < arr[j]) の場合 → k を j+1 から n-1 までループ

ステップ1.1.1.1:

if (arr[j] < arr[k]) の場合 → prod = arr[i] * arr[j] * arr[k] を計算

ステップ1.1.1.2:

if (prod > maxProd) の場合 → maxProd = prod に更新

ステップ2:

maxProd を返す

C++での実装例

#include <iostream>
using namespace std;
int calcMaxProd(int arr[], int n){
    int maxProd = -1000;
    int prod;
    for (int i = 0; i < n - 2; i++)
    for (int j = i + 1; j < n - 1; j++)
    if(arr[i] < arr[j]){
        for (int k = j + 1; k < n; k++){
            if(arr[j] < arr[k]){
                prod = arr[i] * arr[j] * arr[k];
                if(maxProd < prod)
                    maxProd = prod;
            }
        }
    }
    return maxProd;
}
int main(){
    int arr[] = { 5, 9, 2, 11, 4, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The maximum product of an increasing subsequence of size 3 is "<<calcMaxProd(arr, n);
    return 0;
}

出力:

The maximum product of an increasing subsequence of size 3 is 495

この解法は実装が簡単で分かりやすい一方、3重のネストされたループを使用するため、時間計算量は O(n³) となり、配列が大きくなると処理が遅くなります。次に、より効率的な解法を見ていきましょう。

解法2: 効率的な解法（O(n log n)）

効率的な解法では、配列の各要素を「中央の要素」として扱う発想を利用します。インデックス1から n-2 までの各要素 arr[i] に対して、以下の2つの要素を求めます。

• 左側の要素: インデックスが i より小さく、値が arr[i] より小さい最大の要素
• 右側の要素: インデックスが i より大きく、値が arr[i] より大きい最大の要素

左側の小さい要素の探索には自己平衡二分探索木（C++では std::set を利用可能）を使用します。右側の大きい要素については、配列を右から左へ走査しながらそれまでの最大値を更新していくことで求められます。

両方の値が求まれば、3要素の積を計算し、すべての候補と比較しながら maxProd を更新していきます。この方法により、時間計算量を O(n log n) まで抑えることができます。

C++での実装例

#include<bits/stdc++.h>
using namespace std;
long calMaxSubSeqProd(int arr[] , int n) {
    int smallerLeftEle[n];
    smallerLeftEle[0] = -1 ;
    set<int>small ;
    for (int i = 0; i < n ; i++) {
        auto it = small.insert(arr[i]);
        auto val = it.first;
        --val;
        if (val != small.end())
        smallerLeftEle[i] = *val;
        else
        smallerLeftEle[i] = -1;
    }
    long maxProd = -10000;
    long prod ;
    int greaterRightEle = arr[n-1];
    for (int i= n-2 ; i >= 1; i--) {
        if (arr[i] > greaterRightEle)
            greaterRightEle = arr[i];
        else if (smallerLeftEle[i] != -1){
            prod = smallerLeftEle[i]*arr[i]*greaterRightEle;
            if(prod > maxProd)
                maxProd = prod;
        }
    }
    return maxProd;
}
int main() {
    int arr[] = {5, 9, 2, 11, 4, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"The maximum product of an increasing subsequence of size 3 is "<<calMaxSubSeqProd(arr, n);
    return 0;
}

出力:

The maximum product of an increasing subsequence of size 3 is 495

まとめ

サイズ3の増加部分列の最大積を求める問題は、総当たり法では O(n³) の計算量が必要ですが、各要素を中央の要素とみなし、左側の適切な要素を平衡二分探索木で、右側の最大要素を後ろからの走査で求めることで、O(n log n) まで高速化できます。データ量が多い場合は、効率的な解法を選択することが重要です。