数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会学
时尚研究
法律研究最大乘积子数组——在 C++ 中使用两次遍历
在该问题中，我们给出了一个整数数组 arr[]。我们的任务是创建一个程序，在 C++ 中使用两次遍历找到最大乘积子数组。
问题描述 − 在该数组中，我们将使用两次遍历（一次从索引 0 开始，另一次从索引 (n-1) 开始）找到最大乘积子数组。
让我们举个例子来理解这个问题，
输入
arr[] = {4, -2, 5, -6, 0, 8}输出
240
示例
Subarray = {4, -2, 5, -6}
Maximum product = 4 * (-2) * 5 * (-6) = 240解决方法
要使用两次遍历来解决这个问题。在此，我们将使用两个局部最大值来计算从左到右的遍历（即从索引 0 到 n-1）的最大乘积。另一个用于计算从右到左的遍历（即从索引 n-1 到 0）的最大乘积。该算法的其余部分与寻找最大乘积子数组相同。
用于说明我们解决方案的工作原理的程序，
示例
#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
更新时间：2020 年 9 月 15 日
143 次浏览
广告