最大产品子阵列| 在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