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 []包含正整数和负整数。

  • 可变大小包含数组的长度。

  • 函数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