数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++程序中的数组最大乘积子集
在这个问题中，我们得到一个包含n个整数值的数组arr[]。我们的任务是创建一个程序来查找数组的最大乘积子集。
问题描述 − 在这里，我们需要计算数组元素子集的最大可能乘积。
子集 − 如果子集sub[]中的所有元素都存在于数组arr[]中，则sub[]是arr[]的子集。
让我们来看一个例子来理解这个问题：
输入
arr[] = {4, 5, 2, −1, 3}输出
40
解释
Subset sub[] = {4, 5, 2}
Prod = 4*5*2 = 40解决方案方法
解决这个问题的一个简单易行的方法是创建数组的所有可能的子集。找到它们的乘积并返回其中的最大值。
这种解决方案易于实现，但需要嵌套循环，使其复杂度为O(n2*n)。
有效的解决方案是通过计算数组中负数(nofNeg)和零(nof0)的个数，然后根据这些条件计算maxProd。
情况1(nof0 = 0且nofNeg为偶数) - 将数组的所有元素考虑在乘积中。
maxProd = arr[0] * arr[1] * … arr[n−1]
情况2(nof0 = 0且nofNeg为奇数) - 考虑数组中的所有元素，除了数组中最大的负元素（最接近0的）。
情况3(nof0 != 0) - 将数组的所有零排除在乘积之外。并采取与情况1和2类似的情况。
特殊情况 - 只有一个元素（除了0）是负数。maxProd = 0。
算法
初始化 −
maxProd = 1;
步骤1 −
Loop the array and count, nof0(number of zeros) and nofNeg(number of negatives), and find maxProd. maxProd = maxProd*arr[i], i −> 0 to n−1
步骤2 −
consider the following cases − Case 1− if(nofNeg%2 == 0): maxProd Case 2− if(nofNeg%2 != 0): maxProd = maxProd/(largestNeg) Case 3 − if(nof0 == (n-1) and nofNeg == 1), maxProd = 0.
步骤3
Print maxProd.
示例
程序说明了我们解决方案的工作原理：
#include <iostream>
using namespace std;
int findMaxSubsetProd(int arr[], int n){
int larNeg = −1000;
int nofNeg = 0, Nof0 = 0;
int maxProd = 1;
for (int i = 0; i < n; i++) {
if (arr[i] == 0){
Nof0++;
continue;
}
else if (arr[i] < 0) {
nofNeg++;
if(larNeg < arr[i])
larNeg = arr[i];
}
maxProd = maxProd * arr[i];
}
if(nofNeg%2 == 0){
return maxProd;
}
else if(nofNeg%2 != 0)
return (maxProd / larNeg);
if(Nof0 == (n−1) and nofNeg == 1)
return 0;
return maxProd;
}
int main(){
int arr[] = {4, −2, 5, −1, 3, −6};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum product subset of an array is "<<findMaxSubsetProd(arr, n);
return 0;
}输出
The maximum product subset of an array is 720
更新于：2020年12月9日
183 次浏览
广告