C ++プログラムの配列内のトリプレット（サイズ3のサブシーケンス）の最大積。

---

この問題では、n個の整数で構成される配列arr[]が与えられます。私たちのタスクは、配列内のトリプレット（サイズ3のサブシーケンス）の最大積を見つけることです。ここでは、商品の価値が最大のトリプルを見つけて、商品を返品します。

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

入力

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

出力

693

説明

ここでは、配列のすべての要素の最大積を与えるトリプレットを見つけます。 maxProd =9 * 11 * 7 =693

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

この問題には複数の解決策があります。ここでそれらについて話し合います

方法1

直接法この方法では、配列を直接ループして、可能なすべてのトリプレットを見つけます。各トリプレットの要素の積を見つけて、それらすべての最大値を返します。

アルゴリズム

初期化

maxProd = −1000

ステップ1 ：

Create three nested loops:
Loop 1:i −> 0 to n−3
Loop 2: j −> i to n−2
Loop 3: k −> j to n−1

ステップ1.1 −

Find the product, prod = arr[i]*arr[j]*arr[k].

ステップ1.2 −

if prod > maxProd −> maxProd = prod.

ステップ3 −

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++)
   for (int k = j + 1; k < n; k++){
      prod = arr[i] * arr[j] * arr[k];
      if(maxProd < prod)
      maxProd = prod;
   }
   return maxProd;
}
int main(){
   int arr[] = { 9, 5, 2, 11, 7, 4 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum product of a triplet in array is "<<calcMaxProd(arr, n);
   return 0;
}

出力

Maximum product of a triplet in array is 693

方法2

並べ替えの使用

この方法では、配列を降順で並べ替えます。ソートされた配列では、最大の積トリプレットは、

になります。

(arr[0], arr[1], arr[2])
(arr[0], arr[1], arr[2])

これらのトリプレットの製品の最大値を返します。

アルゴリズム

ステップ1 −

Sort the given array in descending order.

ステップ2 −

Find product of triples,
maxTriplet1 = arr[0]*arr[1]*arr[2]
maxTriplet2 = arr[0]*arr[n−1]*arr[n−2]

ステップ3 −

if( maxTriplet1 > maxTriplet2 ) −> return maxTriplet1

ステップ4 −

else −> return maxTriplet2.

例

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

#include <bits/stdc++.h>
using namespace std;
int calcMaxProd(int arr[], int n){
   sort(arr, arr + n, greater<>());
   int maxTriplet1 = arr[0]*arr[1]*arr[2];
   int maxTriplet2 = arr[0]*arr[n−1]*arr[n−2];
   if(maxTriplet1 > maxTriplet2)
      return maxTriplet1;
   return maxTriplet2;
}
int main(){
   int arr[] = { 9, 5, 2, 11, 7, 4 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum product of a triplet in array is
   "<<calcMaxProd(arr, n);
   return 0;
}

出力

アレイ内のトリプレットの最大積は693です

方法3

トリプレット値の検索。

最大の製品トリプレットは2つのトリプレットのいずれかからのものである可能性があることがわかったので、

(maximum, second_max, third_max)
(maximum, minimum, second_min)

したがって、配列をトラバースすることでこれらの値を直接見つけることができ、次に値を使用して、最大の積トリプレットを見つけることができます。

アルゴリズム

初期化

max =-1000、secMax =-1000、thirdMax =-1000、min =10000、secMin =10000

ステップ1 −

loop the array i −> 0 to n−1.

ステップ1.1

if(arr[i] > max) −> thirdMax = secMax, secMax = max, max
= arr[i]

ステップ1.2 −

elseif(arr[i] > secMax) −> thirdMax = secMax, secMax =
arr[i]

ステップ1.3 −

elseif(arr[i] > thirdMax) −> thirdMax = arr[i]

ステップ1.4 −

if(arr[i] < min) −> secMin = min, min = arr[i]

ステップ1.4 −

elseif(arr[i] < secMin) −> secMin = arr[i]

ステップ2 −

triplet1 = max * secMax * thridMax
triplet2 = max * min * secMin

ステップ3 −

if(triplet1 > triplet2) −> return triplet1

ステップ4 −

else −> return triplet2

例

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

#include <iostream>
using namespace std;
int calcMaxProd(int arr[], int n){
   int max = −1000, secMax = −1000, thirdMax = −1000;
   int min = 1000, secMin = 1000;
   for (int i = 0; i < n; i++){
      if (arr[i] > max){
         thirdMax = secMax;
         secMax = max;
         max = arr[i];
      }
      else if (arr[i] > secMax){
         thirdMax = secMax;
         secMax = arr[i];
      }
      else if (arr[i] > thirdMax)
      thirdMax = arr[i];
      if (arr[i] < min){
         secMin = min;
         min = arr[i];
      }
      else if(arr[i] < secMin)
      secMin = arr[i];
   }
   int triplet1 = max * secMax * thirdMax;
   int triplet2 = max * secMin * min;
   if(triplet1 > triplet2)
   return triplet1;
   return triplet2;
}
int main(){
   int arr[] = { 9, 5, 2, 11, 7, 4 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum product of a triplet in array is
   "<<calcMaxProd(arr, n);
   return 0;
}

出力

Maximum product of a triplet in array is 693