最大の製品サブアレイ-C++で2つのトラバーサルを使用

この問題では、整数の配列arr[]が与えられます。私たちのタスクは、最大の製品サブアレイを見つけるプログラムを作成することです-C++で2つのトラバーサルを使用します。

問題の説明 −ここの配列では、1つはインデックス0から、もう1つはインデックス（n-1）からの2つのトラバーサルを使用して、最大の積サブアレイを見つけます。

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

入力

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

出力

240

例

Subarray = {4, -2, 5, -6}
Maximum product = 4 * (-2) * 5 * (-6) = 240

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

2つのトラバーサルを使用してこの問題を解決します。ここでは、左から右へのトラバーサル、つまりインデックス0からn-1への2つのローカル最大値を使用して、maximumproductを見つけます。そして、右から左へのトラバーサル、つまりindexn-1から0へのトラバーサル用です。残りのアルゴリズムは、最大のproductsubarrayを見つけることと同じです。

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

例

#include<iostream>
using namespace std;
int CalcMaxProductSubArray(int arr[], int n) {
   int frntMax = 1, rearMax = 1, maxVal = 1;
   for (int i=0; i<n; i++) {
      frntMax = frntMax*arr[i];
      if (frntMax == 0)
         frntMax = 1;
   }
   for (int i=n-1; i>=0; i--) {
      rearMax = rearMax * arr[i];
      if (rearMax == 0)
         rearMax = 1;
   }
   maxVal = max(frntMax, rearMax);
   return maxVal;
}
int main() {
   int arr[] = {4, -2, 5, -6, 0, 8};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"Maximum product subarray is "<<CalcMaxProductSubArray(arr, n);
   return 0;
}

出力

Maximum product subarray is 240