最大乘积子数组-在C ++中使用两个遍历

在本教程中，我们将讨论一个程序来查找最大乘积子数组-使用两个遍历

为此，我们将提供一个包含正值和负值的数组。我们的任务是在O(n)时间复杂度内找到子阵列的最大乘积。

示例

#include<bits/stdc++.h>
using namespace std;
//finding maximum product
int max_product(int arr[], int n) {
   int max_fwd = INT_MIN, max_bkd = INT_MIN;
   int max_till_now = 1;
   bool isZero=false;
   for (int i=0; i<n; i++) {
      max_till_now = max_till_now*arr[i];
      if (max_till_now == 0) {
         isZero=true;
         max_till_now = 1;
         continue;
      }
      if (max_fwd < max_till_now)
         max_fwd = max_till_now;
   }
   max_till_now = 1;
   for (int i=n-1; i>=0; i--) {
      max_till_now = max_till_now * arr[i];
      if (max_till_now == 0) {
         isZero=true;
         max_till_now = 1;
         continue;
      }
      if (max_bkd < max_till_now)
         max_bkd = max_till_now;
   }
   int res = max(max_fwd, max_bkd);
   if(isZero)
      return max(res, 0);
   return res;
}
int main() {
   int arr[] = {-1, -2, -3, 4};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << max_product(arr, n) << endl;
   return 0;
}

输出结果

24