C ++の配列の最大積4倍（サイズ4のサブシーケンス）

この問題では、配列arr[]が与えられます。私たちのタスクは、C ++の配列で最大積の4倍（サイズ4のサブシーケンス）を見つけるプログラムを作成することです。

コードの説明 −ここでは、すべての要素の積が最大になるように、4つ（サイズ4のサブシーケンス）を見つける必要があります。

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

入力

arr[] = {4, -2, 5, -6, 8}

出力

840

説明

製品840の4つ組（-3、5、-7、8）。

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

特定の問題には複数の解決策があります。

簡単な解決策の1つは、配列をトラバースすることによる直接法を使用することです。次に、配列内のすべての可能な4倍を見つけます。彼らの製品を見つけ、それを比較して最大の製品の4倍を見つけます。

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

例

#include <iostream>
using namespace std;
int max(int a, int b){
   if(a > b)
      return a;
      return b;
}
int findMaxProdQuad(int arr[], int n){
   int maxProd = 0;
   int prod = 1;
   for (int i = 0; i <= n - 4; i++)
   for (int j = i + 1; j <= n - 3; j++)
   for (int k = j + 1; k <= n - 2; k++)
   for (int l = k + 1; l <= n - 1; l++) {
      prod = arr[i] * arr[j] * arr[k] * arr[l];
      maxProd = max(maxProd, prod);
      prod = 1;
   }
   return maxProd;
}
int main(){
   int arr[] = {4, -2, 5, -6, 8};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum product of quadruple is "<<findMaxProdQuad(arr, n);
   return 0;
}

出力

Maximum product of quadruple is 480

最大積の4倍を見つける別の方法は、配列の4つの最大要素と配列の4つの最小要素を見つけることです。

mx1、mx2、mx3、mx4が最初の4つの最大数であるとしましょう。また、mn1、mn2、mn3、mn4は、配列の最初の4つの最小数です。次に、

1. mx1 * mx2 * mx3 * mx4
2. mn1 * mn2 * mn3 * mn4
3. mx1 * mx2 * mn1 * mn2

そして、これら3つの製品値の最大値を返します。これにより、最大の製品が4倍になります。そして、すべてのケースが考慮されます。

アルゴリズムの実装を示すプログラム

例

#include <iostream>
using namespace std;
int max(int a, int b){
   if(a > b)
      return a;
      return b;
}
int findMaxProdQuad(int arr[], int n) {
   int mx1 = -1000, mx2 = -1000, mx3 = -10000, mx4 = -1000;
   int mn1 = 1000, mn2 = 1000, mn3 = 1000, mn4 = 1000;
   for (int i = 0; i < n; i++) {
      if(arr[i] < mn1){
         mn4 = mn3;
         mn3 = mn2;
         mn2 = mn1;
         mn1 = arr[i];
      }
      else if(arr[i] < mn2){
         mn4 = mn3;
         mn3 = mn2;
         mn2 = arr[i];
      }
      else if(arr[i] < mn3){
         mn4 = mn3;
         mn3 = arr[i];
      }
      else if(arr[i] < mn4){
         mn4 = arr[i];
      }
      if(arr[i] > mx1){
         mx4 = mx3;
         mx3 = mx2;
         mx2 = mx1;
         mx1 = arr[i];
      }
      else if(arr[i] > mx2){
         mx4 = mx3;
         mx3 = mx2;
         mx2 = arr[i];
      }
      else if(arr[i] > mx3){
         mx4 = mx3;
         mx3 = arr[i];
      }
      else if(arr[i] > mx4){
         mx4 = arr[i];
      }
   }
   int maxVal = max ((mx1 * mx2 * mx3 * mx4), (mn1 * mn2 * mn3 * mn4));
   maxVal = max(maxVal, (mx1 * mx2 * mn1 * mn2));
   return maxVal;
}
int main() {
   int arr[] = {4, -2, 5, -6, 8};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum product of quadruple is "<<findMaxProdQuad(arr, n);
   return 0;
}

出力

Maximum product of quadruple is 480

もう1つのアプローチは、配列をソートすることです。次に、4つの最大値と4つの最小値が、それぞれアレイの終了と開始になります。次に、最大値と最小値の3つの組み合わせの最大値を見つけて、上記のソリューションのように解きます。

私たちのアプローチの実装を示すプログラム

例

#include <bits/stdc++.h>
using namespace std;
int findMaxProdQuad(int arr[], int n){
   sort(arr, arr + n);
   int maxVal = max((arr[n-1] * arr[n-2] * arr[n-3] * arr[n-4]), (arr[0] *
   arr[1] * arr[2] * arr[3]));
   maxVal = max(maxVal, (arr[n-1] * arr[n-2] * arr[0] * arr[1]));
   return maxVal;
}
int main(){
   int arr[] = {4, -2, 5, -6, 8};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum product of quadruple is "<<findMaxProdQuad(arr, n);
   return 0;
}

出力

Maximum product of quadruple is 480