数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学最大乘积子数组 | C++ 中添加负乘积案例
在这个问题中，我们得到一个整数数组（包含正数和负数）。我们的任务是创建一个 C++ 程序来计算最大乘积子数组。
问题解答 − 这里，我们有一个包含正数、负数和零的数组。我们需要找到由数组元素创建的子数组的乘积，并使子数组的乘积最大化。
让我们举个例子来理解这个问题：
输入
arr[] = {-1, 2, -7, -5, 12, 6}输出
5040
解释
乘积最大的子数组是 {2, -7, -5, 12, 6}
Product = 5040
解决方案方法
为了解决这个问题，我们得到一个数组和子数组的最大乘积，并维护 maxVal（当前元素之前的最大乘积）和 minVal（当前元素之前的负最大乘积）。然后根据当前值，更新 maxVal 和 minVal，如下所示：
情况 1 - 元素为正数 − 通过乘以数组来更新 maxVal 和 minVal。
情况 2 - 元素为零 − 中断当前子数组，因为乘以 0 将导致结果为 0。
情况 3 - 元素为负数 − 使用负值更新两个值，使其成为最大值。
程序说明了我们解决方案的工作原理：
示例
#include <iostream>
using namespace std;
int min(int a, int b){
if(a < b)
return a;
return b;
}
int max(int a, int b){
if(a > b)
return a;
return b;
}
int CalcMaxProductSubArray(int arr[], int n) {
int i = 0;
int maxVal = -1000;
int localMax = 1;
int localMin = 1;
int lastMax;
while(i < n) {
int currentVal = arr[i];
if (currentVal > 0) {
localMax = (localMax * currentVal);
localMin = min(1, localMin * currentVal);
}
else if (currentVal < 0) {
lastMax = localMax;
localMax = (localMin * currentVal);
localMin = (lastMax * currentVal);
} else {
localMin = 1;
localMax = 0;
}
maxVal = max(maxVal, localMax);
if (localMax <= 0)
localMax = 1;
i++;
}
return maxVal;
}
int main(){
int arr[] = { -1, 2, -7, -5, 12, 6 };
int n = 6;
cout<<"The maximum product Subarray is "<<CalcMaxProductSubArray(arr, n);
return 0;
}输出
The maximum product Subarray is 5040
更新于：2020年9月15日
浏览量 125 次
广告