C++での最大および最小製品サブセット

サイズNの整数の配列が与えられます。ここでの目標は、最大および最小の積サブセットを見つけることです。これを行うには、2つの製品変数を使用します。1つはこれまでに見つかった最小の製品minProdで、もう1つはこれまでに見つかった最大の製品maxProdです。

配列をトラバースしている間、各要素にminProdとmaxProdの両方を乗算します。また、以前の最大製品、以前の最小製品、現在の最大製品、現在の最小製品、および現在の要素自体もチェックしてください。

入力

Arr[]= { 1,2,5,0,2 }

出力

Maximum Product: 20
Minimum Product: 0

説明 − maxProd値とminProd値が1（最初の要素）で初期化された配列の2番目の要素から開始します。

Arr[1]: 1*2=2, 1*2=2, maxProd=2, minProd=1
Arr[2]: 2*5=10, 1*5=5, maxProd=10, minProd=1
Arr[3]: 10*0=0, 1*0=0, maxProd=10, minProd=0
Arr[4]: 10*2=20, 0*2=0, maxProd=20, minProd=0

入力

Arr[]= { -1,2,-5,0,2 }

出力

Maximum Product: 20
Minimum Product: -20

説明 −最大の積の場合、サブセットには要素があります-{-1,2、-5,2}

最小の製品の場合、サブセットには要素があります-{2、-5,2}

以下のプログラムで使用されているアプローチは次のとおりです

• 整数配列Arr[]には、正の整数と負の整数が含まれています。

• 可変サイズには配列の長さが含まれます。

• 関数getProductSubset（int arr []、int n）は、配列を入力として受け取り、取得された要素の最大値と最小値の積を返します。

• 変数curMin、curMaxは、検出された現在の最大および最小の積を格納するために使用されます。最初はarr[0]。

• 変数prevMin、prevMaxは、以前に見つかった最大および最小の積を格納するために使用されます。最初はarr[0]。

• 変数maxProdおよびminProdは、取得された最終的な最大および最小の積を格納するために使用されます。

• 2番目の要素であるarr[1]から最後のインデックスまで配列のトラバースを開始します。

• 最大の積を得るには、現在のarr[i]にprevMaxおよびprevMinを掛けます。最大の製品をcurMaxに保存します。このcurMax>prevMaxの場合、curMaxをprevMaxで更新します。

• curMax> maxProdの場合、maxProdをcurMaxで更新します。

• 最後に、次の反復のためにprevMaxをcurMaxで更新します。

• 比較を変更して、prevMin、curMin、およびminProdに対して上記と同じ手順を実行します。

• ループが終了した後、maxProdとminProdで得られた結果を印刷します。

例

#include <iostream>
using namespace std;
void getProductSubset(int arr[], int n){
   // Initialize all products with arr[0]
   int curMax = arr[0];
   int curMin = arr[0];
   int prevMax = arr[0];
   int prevMin= arr[0];
   int maxProd = arr[0];
   int minProd = arr[0];
   int temp1=0,temp2=0,temp3=0;
   // Process all elements after arr[0]
   for (int i = 1; i < n; ++i){
      /* Current maximum product is maximum of following
      1) prevMax * current arr[i] (when arr[i] is +ve)
      2) prevMin * current arr[i] (when arr[i] is -ve)
      3) current arr[i]
      4) Previous max product */
      temp1=prevMax*arr[i];
      temp2=prevMin*arr[i];
      temp3=temp1>temp2?temp1:temp2;
      curMax = temp3>arr[i]?temp3:arr[i];
      curMax = curMax>prevMax?curMax:prevMax;
      /* Current minimum product is minimum of following
      1) prevMin * current arr[i] (when arr[i] is +ve)
      2) prevMax * current arr[i] (when arr[i] is -ve)
      3) current arr[i]
      4) Previous min product */
      temp1=prevMax*arr[i];
      temp2=prevMin*arr[i];
      temp3=temp1<temp2?temp1:temp2;
      curMin = temp3<arr[i]?temp3:arr[i];
      curMin = curMin<prevMin?curMin:prevMin;
      maxProd = maxProd>curMax?maxProd:curMax;
      minProd = minProd<curMin?minProd:curMin;
      // copy current values to previous values
      prevMax = curMax;
      prevMin = curMin;
   }
   std::cout<<"Maximum Subset Product: "<<maxProd;
   std::cout<<"\nMinimum Subset Product: "<<minProd;
}
int main(){
   int Arr[] = {-4, -3, 1, 2, 0, 8, 1};
   // int arr[] = {-4, 1,1, 3, 5,7};
   int size = 7;
   getProductSubset(Arr,size ) ;
   return 0;
}

出力

Maximum Subset Product: 192
Minimum Subset Product: -64