C++でのサイズkのサブシーケンスの最大積

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

問題の説明 −ここで、要素の最大積を持つサイズk、1 <=k<=nのサブシーケンスを見つける必要があります。

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

入力

arr[] = {1, 5, 6, -2, 0, 4} , k = 3

出力

120

説明

最大の積を持つサイズ3のサブシーケンスは（5、6、4）です。製品は120です。

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

この問題を解決するために、最初に配列arr []をソートし、次にarr[]の要素とkの値に基づいてソートします。方法は次のように変わります-

ケース1（kが偶数の場合） −積は、0を除くすべての最大k値を持つことができます。ここでは、負の値のペアも考慮する必要があります。それらの大きさも最大の結果を与えることができるので。

ケース2（kが奇数の場合） −これは少し複雑な条件であり、値は結果の計算方法を定義します。このケースは、配列の最大要素に基づいてさらに分類する必要があります。

ケース2.1（最大数が正の場合） −これは、配列が正の数と負の数の混合であることを意味します。この場合、最大k個の要素を見つけ、負の側から最大ペアを検索します（可能であれば結果が得られる可能性があります）。

ケース2.2（最大数がゼロの場合） −これは、配列にすべての負の要素とゼロが含まれていることを意味します。この場合、負の要素の奇数を乗算すると負の数になるため、最大結果は0になります。これは、0が最大の積であることを意味します。

ケース2.3（最大数が負の場合） −これは、配列に負の数のみが含まれていることを意味します。この場合、最大の結果は、最小の大きさで要素を乗算することによって提供されます。つまり、最大の配列が役立ちます。

このように、最適な結果を得るには、要素の値とkをチェックする必要があります。このために、最大値と最小値の両側を配列に保持して、結果に負のペアを乗算することで結果が得られるかどうかを確認します。

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

例

#include <bits/stdc++.h>
using namespace std;
int findMaxSubArrayProduct(int arr[], int n, int k) {
   sort(arr, arr + n);
   int maxProd = 1;
   int i = 0, j = 0;
   int maxprod, minprod;
   if (arr[n - 1] == 0 && (k % 2 == 1))
      return 0;
   if (arr[n - 1] <= 0 && (k % 2 == 1)) {
      for (i = n - 1; i >= n - k; i--)
         maxProd *= arr[i];
         return maxProd;
   }
   i = 0;
   j = n - 1;
   if (k % 2 == 1) {
      maxProd *= arr[j];
      j--;
      k--;
   }
   k = k/2;
   int it = 0;
   while(it < k){
      int minprod = arr[i] * arr[i + 1];
      int maxprod = arr[j] * arr[j - 1];
      if (minprod > maxprod) {
         maxProd *= minprod;
         i += 2;
      } else {
         maxProd *= maxprod;
         j -= 2;
      }
      it++;
   }
   return maxProd;
}
int main() {
   int arr[] = { 1, 5, 6, -2, 0, 4 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 3;
   cout<<"The maximum product of subsequence of size "<<k<<" is "<<findMaxSubArrayProduct(arr, n, k);
   return 0;
}

出力

The maximum product of subsequence of size 3 is 120