数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中的最大和最小乘积子集
给定一个大小为N的整数数组。这里的目标是找到最大和最小乘积子集。我们将通过使用两个乘积变量来实现这一点，一个用于迄今为止找到的最小乘积`minProd`，另一个用于迄今为止找到的最大乘积`maxProd`。
在遍历数组时，我们将每个元素分别与`minProd`和`maxProd`相乘。还要检查之前的最大乘积、之前的最小乘积、当前最大乘积、当前最小乘积以及当前元素本身。
输入
Arr[]= { 1,2,5,0,2 }输出
Maximum Product: 20 Minimum Product: 0
解释 − 从数组中的第二个元素开始，`maxProd`和`minProd`的值初始化为1（第一个元素）。
Arr[1]: 1*2=2, 1*2=2, maxProd=2, minProd=1 Arr[2]: 2*5=10, 1*5=5, maxProd=10, minProd=1 Arr[3]: 10*0=0, 1*0=0, maxProd=10, minProd=0 Arr[4]: 10*2=20, 0*2=0, maxProd=20, minProd=0
输入
Arr[]= { -1,2,-5,0,2 }输出
Maximum Product: 20 Minimum Product: -20
解释 − 对于最大乘积，子集的元素为{-1, 2, -5, 2}
对于最小乘积，子集的元素为{2, -5, 2}
下面程序中使用的方法如下
整数数组`Arr[]`包含正整数和负整数。
变量`size`包含数组的长度。
函数`getProductSubset(int arr[], int n)`以数组作为输入，并返回获得的元素的最大和最小乘积。
变量`curMin`、`curMax`用于存储当前找到的最大和最小乘积。初始值为`arr[0]`。
变量`prevMin`、`prevMax`用于存储先前找到的最大和最小乘积。初始值为`arr[0]`。
变量`maxProd`和`minProd`用于存储最终获得的最大和最小乘积。
从第二个元素`arr[1]`开始遍历数组，直到最后一个索引。
对于最大乘积，将当前`arr[i]`与`prevMax`和`prevMin`相乘。将最大乘积存储在`curMax`中。如果`curMax > prevMax`，则用`prevMax`更新`curMax`。
如果`curMax > maxProd`，则用`curMax`更新`maxProd`。
最后，为下一次迭代将`prevMax`更新为`curMax`。
通过更改比较，对`prevMin`、`curMin`和`minProd`执行与上述相同的步骤。
循环结束后，打印`maxProd`和`minProd`中获得的结果。
示例
#include <iostream>
using namespace std;
void getProductSubset(int arr[], int n){
// Initialize all products with arr[0]
int curMax = arr[0];
int curMin = arr[0];
int prevMax = arr[0];
int prevMin= arr[0];
int maxProd = arr[0];
int minProd = arr[0];
int temp1=0,temp2=0,temp3=0;
// Process all elements after arr[0]
for (int i = 1; i < n; ++i){
/* Current maximum product is maximum of following
1) prevMax * current arr[i] (when arr[i] is +ve)
2) prevMin * current arr[i] (when arr[i] is -ve)
3) current arr[i]
4) Previous max product */
temp1=prevMax*arr[i];
temp2=prevMin*arr[i];
temp3=temp1>temp2?temp1:temp2;
curMax = temp3>arr[i]?temp3:arr[i];
curMax = curMax>prevMax?curMax:prevMax;
/* Current minimum product is minimum of following
1) prevMin * current arr[i] (when arr[i] is +ve)
2) prevMax * current arr[i] (when arr[i] is -ve)
3) current arr[i]
4) Previous min product */
temp1=prevMax*arr[i];
temp2=prevMin*arr[i];
temp3=temp1<temp2?temp1:temp2;
curMin = temp3<arr[i]?temp3:arr[i];
curMin = curMin<prevMin?curMin:prevMin;
maxProd = maxProd>curMax?maxProd:curMax;
minProd = minProd<curMin?minProd:curMin;
// copy current values to previous values
prevMax = curMax;
prevMin = curMin;
}
std::cout<<"Maximum Subset Product: "<<maxProd;
std::cout<<"\nMinimum Subset Product: "<<minProd;
}
int main(){
int Arr[] = {-4, -3, 1, 2, 0, 8, 1};
// int arr[] = {-4, 1,1, 3, 5,7};
int size = 7;
getProductSubset(Arr,size ) ;
return 0;
}输出
Maximum Subset Product: 192 Minimum Subset Product: -64
浏览量：288
