最大乘积子数组-在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