最大产品子阵列| 在C ++中添加了否定产品案例

在本教程中，我们将讨论一个程序来查找具有负乘积情况的最大乘积子数组。

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

示例

#include <bits/stdc++.h>
using namespace std;
//查找最大乘积子数组
int findMaxProduct(int arr[], int n) {
   int i;
   int ans = INT_MIN;
   int maxval = 1;
   int minval = 1;
   int prevMax;
   for (i = 0; i < n; i++) {
      if (arr[i] > 0) {
         maxval = maxval * arr[i];
         minval = min(1, minval * arr[i]);
      }
      else if (arr[i] == 0) {
         minval = 1;
         maxval = 0;
      }
      else if (arr[i] < 0) {
         prevMax = maxval;
         maxval = minval * arr[i];
         minval = prevMax * arr[i];
      }
      ans = max(ans, maxval);
      if (maxval <= 0) {
         maxval = 1;
      }
   }
   return ans;
}
int main() {
   int arr[] = { 0, -4, 0, -2 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << findMaxProduct(arr, n);
   return 0;
}

输出结果

0