C++プログラムの配列の最大積サブセット

この問題では、n個の整数値の配列arr[]が与えられます。私たちのタスクは、配列の最大積サブセットを見つけるプログラムを作成することです。

問題の説明 −ここでは、配列の要素のサブセットの可能な最大積を計算する必要があります。

サブセット − sub[]のすべての要素がarr[]に存在する場合、配列sub[]は配列arr[]のサブセットです。

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

入力

arr[] = {4, 5, 2, −1, 3}

出力

40

説明

Subset sub[] = {4, 5, 2}
Prod = 4*5*2 = 40

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

問題を解決するためのシンプルで簡単なアプローチは、アレイのすべての可能なサブセットを作成することです。彼らの製品を見つけて、それらの最大数を返します。

このソリューションは実装が簡単ですが、ネストされたループが必要であり、O（n ² のオーダーの複雑さを実現します。 * n）。

ここで実装してみてください。

効果的なソリューション 配列から負の数（nofNeg）とゼロの数（nof0）を計算し、これらの条件に基づいてmaxProdを計算します。

ケース1 （nof0 =0で、nofNegは偶数です）-配列のすべての要素を積に考慮します。

maxProd =arr [0] * arr[1]*…arr[n-1]

ケース2 （nof0 =0およびnofNegは奇数）-配列の最大の負の要素（0に最も近い）を除く配列のすべての要素を考慮します。

ケース3 （nof0！=0）-積の配列のすべてのゼロを残します。そして、ケース1と2と同様のケースを取ります。

特別な場合 −0以外の1つの要素のみが負です。 maxProd=0。

アルゴリズム

初期化 −

maxProd = 1;

ステップ1 −

Loop the array and count, nof0(number of zeros) and
nofNeg(number of negatives), and find maxProd.
maxProd = maxProd*arr[i], i −> 0 to n−1

ステップ2 −

consider the following cases −
Case 1− if(nofNeg%2 == 0): maxProd
Case 2− if(nofNeg%2 != 0): maxProd = maxProd/(largestNeg)
Case 3 − if(nof0 == (n-1) and nofNeg == 1), maxProd = 0.

ステップ3

Print maxProd.

例

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

#include <iostream>
using namespace std;
int findMaxSubsetProd(int arr[], int n){
   int larNeg = −1000;
   int nofNeg = 0, Nof0 = 0;
   int maxProd = 1;
   for (int i = 0; i < n; i++) {
      if (arr[i] == 0){
         Nof0++;
         continue;
      }
      else if (arr[i] < 0) {
         nofNeg++;
         if(larNeg < arr[i])
         larNeg = arr[i];
      }
      maxProd = maxProd * arr[i];
   }
   if(nofNeg%2 == 0){
      return maxProd;
   }
   else if(nofNeg%2 != 0)
      return (maxProd / larNeg);
   if(Nof0 == (n−1) and nofNeg == 1)
      return 0;
   return maxProd;
}
int main(){
   int arr[] = {4, −2, 5, −1, 3, −6};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum product subset of an array is "<<findMaxSubsetProd(arr, n);
   return 0;
}

出力

The maximum product subset of an array is 720