给定一个大小为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 []包含正整数和负整数。
可变大小包含数组的长度。
函数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。
最后,使用curMax更新prevMax,以进行下一次迭代。
通过更改比较,对prevMin,curMin和minProd执行与上述相同的步骤。
循环结束后,打印在maxProd和minProd中获得的结果。
#include <iostream> using namespace std; void getProductSubset(int arr[], int n){ //初始化所有产品 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; //之后的所有元素 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; //将当前值复制到以前的值 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