【C++】サイズ3の増加部分列における最大積の効率的な求め方

はじめに

本記事では、C++を用いて「サイズ3の増加部分列の最大積」を求めるプログラムについて解説します。

具体的には、正の整数からなる配列が与えられたとき、その中から3つの要素を選んで値が増加していく部分列を作り、その積が最大になる組み合わせを見つけるという問題です。

アルゴリズムの考え方

増加する3つの要素 a < b < c の積を最大化するには、各要素を「中央の要素」として考えます。手順は以下のとおりです。

• 左側の探索： 注目している要素より左にあり、かつその要素より小さい値のうち、最大のものを求めます。
• 右側の探索： 注目している要素より右側にある値のうち、最大のものを求めます。
• 積の計算： 「左側の最大小値 × 中央の値 × 右側の最大値」を計算し、その最大値を答えとして記録していきます。

std::set を使うと、要素を挿入しながら「自身より小さい直近の値」を効率よく参照できるため、左側の探索を高速に行えます。

C++による実装例

#include<bits/stdc++.h>
using namespace std;
//部分列の最大積を返す
long long int maxProduct(int arr[] , int n) {
   int smaller[n];
   smaller[0] = -1 ;
   set<int>S ;
   for (int i = 0; i < n ; i++) {
      auto j = S.insert(arr[i]);
      auto itc = j.first;
      --itc;
      if (itc != S.end())
         smaller[i] = *itc;
      else
         smaller[i] = -1;
   }
   long long int result = INT_MIN;
   int max_right = arr[n-1];
   for (int i=n-2 ; i >= 1; i--) {
      if (arr[i] > max_right)
         max_right = arr[i];
      else if (smaller[i] != -1)
         result = max(smaller[i] * arr[i] * max_right, result);
   }
   return result;
}
int main() {
   int arr[] = {10, 11, 9, 5, 6, 1, 20};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << maxProduct(arr, n) << endl;
   return 0;
}

実行結果

2200

結果の解説

サンプル配列 {10, 11, 9, 5, 6, 1, 20} の場合、増加する部分列「10, 11, 20」を選ぶと、積は 10 × 11 × 20 = 2200 となり、これが最大値になります。

コードのポイント

前半のループでは std::set に要素を順に挿入し、set が自動的にソート済みの状態を保つ性質を利用して「現在の要素より小さい値の最大値」を配列 smaller に記録しています。

後半のループでは配列を右から左へ走査しながら右側の最大値 max_right を更新し、中央の要素より大きな値が右側に存在する場合に積を計算して結果を更新します。

まとめ

左側の「自分より小さい値の最大」と右側の最大値を事前に用意・逐次更新することで、サイズ3の増加部分列の最大積を効率的に求められます。この手法は、部分列に関する他の最適化問題にも応用できるテクニックなので、ぜひ習得しておきましょう。