最大製品サブアレイ| C++でネガティブな製品ケースを追加しました

この問題では、整数の配列（正と負）が与えられます。私たちのタスクは、C++で最大ProductSubarrayを計算するプログラムを作成することです。

問題の解決策 −ここに、正、負、およびゼロの数を含む配列があります。配列の要素によって作成されたサブ配列の積を見つける必要があります。そして、サブアレイの積を最大化します。

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

入力

arr[] = {-1, 2, -7, -5, 12, 6}

出力

5040

説明

最大積のサブアレイは{2、-7、-5、12、6}

Product = 5040

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

この問題を解決するために、配列とサブ配列の最大積が与えられ、現在の要素までの最大積であるmaxValと、積の負の最大値であるminValを管理します。次に、現在の値に基づいて、maxValとminValが-

ケース1-要素はポジティブです −配列を乗算してmaxValとminValを更新します。

ケース2-要素はゼロです −現在のサブアレイを分割します。0を掛けると0になります。

ケース3-要素が負です −両方の値を負の値で更新して最大にします。

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

例

#include <iostream>
using namespace std;
int min(int a, int b){
   if(a < b)
      return a;
      return b;
}
int max(int a, int b){
   if(a > b)
      return a;
      return b;
}
int CalcMaxProductSubArray(int arr[], int n) {
   int i = 0;
   int maxVal = -1000;
   int localMax = 1;
   int localMin = 1;
   int lastMax;
   while(i < n) {
      int currentVal = arr[i];
      if (currentVal > 0) {
         localMax = (localMax * currentVal);
         localMin = min(1, localMin * currentVal);
      }
      else if (currentVal < 0) {
         lastMax = localMax;
         localMax = (localMin * currentVal);
         localMin = (lastMax * currentVal);
      } else {
         localMin = 1;
         localMax = 0;
      }
      maxVal = max(maxVal, localMax);
      if (localMax <= 0)
         localMax = 1;
         i++;
   }
   return maxVal;
}
int main(){
   int arr[] = { -1, 2, -7, -5, 12, 6 };
   int n = 6;
   cout<<"The maximum product Subarray is "<<CalcMaxProductSubArray(arr, n);
   return 0;
}

出力

The maximum product Subarray is 5040