C++プログラムでサイズ3の増加するサブシーケンスの最大積

この問題では、n個の正の整数の配列arr[]が与えられます。私たちのタスクは、サイズ3の増加するサブシーケンスの最大積を見つけるプログラムを作成することです。

問題の説明 −ここでは、配列の3つの要素の最大積を見つけて、それらが増加するサブシーケンスを形成し、配列インデックスも増加するようにする必要があります。つまり、

arr[i]*arr[j]*arr[k] is maximum,
arr[i]<arr[j]<arr[k] and i<j<k

問題を理解するために例を見てみましょう

入力

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

出力

495

説明

All subarrays of size 3 satisfying the condition are
(5, 9, 11), prod = 5*9*11 = 495
(2, 4, 7), prod = 2*4*7 = 56
Maximum = 495

ソリューションアプローチ

問題を解決するための簡単なアプローチは、配列をループし、指定された条件を満たす3のすべてのサブ配列を見つけることです。

要素の積を見つけて、すべての積の最大値を返します。

アルゴリズム

初期化 −

maxProd = −1000

ステップ1 −

Loop i −> 0 to n−3

ステップ1.1 −

Loop j −> i to n−2

ステップ1.1.1 −

if(arr[i]< arr[j]) −> loop k −> j to n−1

ステップ1.1.1.1 −

if(arr[j] < arr[k]) −> find prod =
arr[i]*arr[j]*arr[k].

ステップ1.1.1.2 −

if(maxProd > prod) −> maxProd = prod.

ステップ2 −

Return maxProd.

例

ソリューションの動作を説明するプログラム

#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（n3）の順序の時間計算量が大きくなります。それでは、問題の効率的な解決策を見てみましょう。

このソリューションでは、インデックス1からn-2までの配列の要素を取得します。そして、それを3要素サブアレイの中央要素として扱います。次に、配列から残りの2つの要素を見つけます。

Element smaller than arr[i] in array with index less than i.
Element greater than aar[i] in array with index more than i.

最小の要素は、自己平衡二分探索木を使用して検出され、最大の要素は、右から左にトラバースして、右の最大要素を検索します。

両方の値を見つけた後、要素サブ配列のprodを見つけ、次にすべてを比較してmaxProdを見つけます。

例

ソリューションの動作を説明するプログラム

#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