数组的最小乘积子集-yiteyi-C++库

给定一个数组a，我们必须找到数组中元素子集的最小乘积。最小乘积也可以是单个元素。

null

例如：

Input : a[] = { -1, -1, -2, 4, 3 }Output : -24Explanation : Minimum product will be ( -2 * -1 * -1 * 4 * 3 ) = -24Input : a[] = { -1, 0 }Output : -1Explanation : -1(single element) is minimum product possible Input : a[] = { 0, 0, 0 }Output : 0

一个简单的解决办法是生成所有子集，找到每个子集的乘积并返回最小乘积。更好的解决方法是使用以下事实。

如果有偶数个负数且没有零，则结果是除最大值负数外的所有负数的乘积。
如果有一个奇数的负数而没有零，结果就是所有的乘积。
如果有零和正，没有负，结果是0。例外情况是，当没有负数，所有其他元素都是正数时，我们的结果应该是第一个最小正数。

C++

                         // CPP program to find maximum product of                       
                         // a subset.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         int                                     minProductSubset(                                     int                                     a[],                                     int                                     n)                       
                         {                       
                                                 if                                     (n == 1)                       
                                                 return                                     a[0];                       
           
                                                 // Find count of negative numbers, count                       
                                                 // of zeros, maximum valued negative number,                       
                                                 // minimum valued positive number and product                       
                                                 // of non-zero numbers                       
                                                 int                                     max_neg = INT_MIN;                       
                                                 int                                     min_pos = INT_MAX;                       
                                                 int                                     count_neg = 0, count_zero = 0;                       
                                                 int                                     prod = 1;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
           
                                                 // If number is 0, we don't                       
                                                 // multiply it with product.                       
                                                 if                                     (a[i] == 0) {                       
                                                 count_zero++;                       
                                                 continue                                     ;                       
                                                 }                       
           
                                                 // Count negatives and keep                       
                                                 // track of maximum valued negative.                       
                                                 if                                     (a[i] < 0) {                       
                                                 count_neg++;                       
                                                 max_neg = max(max_neg, a[i]);                       
                                                 }                       
           
                                                 // Track minimum positive                       
                                                 // number of array                       
                                                 if                                     (a[i] > 0)                       
                                                 min_pos = min(min_pos, a[i]);                       
           
                                                 prod = prod * a[i];                       
                                                 }                       
           
                                                 // If there are all zeros                       
                                                 // or no negative number present                       
                                                 if                                     (count_zero == n                       
                                                 || (count_neg == 0 && count_zero > 0))                       
                                                 return                                     0;                       
           
                                                 // If there are all positive                       
                                                 if                                     (count_neg == 0)                       
                                                 return                                     min_pos;                       
           
                                                 // If there are even number of                       
                                                 // negative numbers and count_neg not 0                       
                                                 if                                     (!(count_neg & 1) && count_neg != 0) {                       
           
                                                 // Otherwise result is product of                       
                                                 // all non-zeros divided by maximum                       
                                                 // valued negative.                       
                                                 prod = prod / max_neg;                       
                                                 }                       
           
                                                 return                                     prod;                       
                         }                       
           
                         int                                     main()                       
                         {                       
                                                 int                                     a[] = { -1, -1, -2, 4, 3 };                       
                                                 int                                     n =                                     sizeof                                     (a) /                                     sizeof                                     (a[0]);                       
                                                 cout << minProductSubset(a, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find maximum product of                       
                         // a subset.                       
                         class                                     GFG {                       
           
                                                 static                                     int                                     minProductSubset(                                     int                                     a[],                                     int                                     n)                       
                                                 {                       
                                                 if                                     (n ==                                     1                                     )                       
                                                 return                                     a[                                     0                                     ];                       
           
                                                 // Find count of negative numbers,                       
                                                 // count of zeros, maximum valued                       
                                                 // negative number, minimum valued                       
                                                 // positive number and product of                       
                                                 // non-zero numbers                       
                                                 int                                     negmax = Integer.MIN_VALUE;                       
                                                 int                                     posmin = Integer.MAX_VALUE;                       
                                                 int                                     count_neg =                                     0                                     , count_zero =                                     0                                     ;                       
                                                 int                                     product =                                     1                                     ;                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++) {                       
           
                                                 // if number is zero,count it                       
                                                 // but dont multiply                       
                                                 if                                     (a[i] ==                                     0                                     ) {                       
                                                 count_zero++;                       
                                                 continue                                     ;                       
                                                 }                       
           
                                                 // count the negative numbers                       
                                                 // and find the max negative number                       
                                                 if                                     (a[i] <                                     0                                     ) {                       
                                                 count_neg++;                       
                                                 negmax = Math.max(negmax, a[i]);                       
                                                 }                       
           
                                                 // find the minimum positive number                       
                                                 if                                     (a[i] >                                     0                                     && a[i] < posmin)                       
                                                 posmin = a[i];                       
           
                                                 product *= a[i];                       
                                                 }                       
           
                                                 // if there are all zeroes                       
                                                 // or zero is present but no                       
                                                 // negative number is present                       
                                                 if                                     (count_zero == n                       
                                                 || (count_neg ==                                     0                                     && count_zero >                                     0                                     ))                       
                                                 return                                     0                                     ;                       
           
                                                 // If there are all positive                       
                                                 if                                     (count_neg ==                                     0                                     )                       
                                                 return                                     posmin;                       
           
                                                 // If there are even number except                       
                                                 // zero of negative numbers                       
                                                 if                                     (count_neg %                                     2                                     ==                                     0                                     && count_neg !=                                     0                                     ) {                       
           
                                                 // Otherwise result is product of                       
                                                 // all non-zeros divided by maximum                       
                                                 // valued negative.                       
                                                 product = product / negmax;                       
                                                 }                       
           
                                                 return                                     product;                       
                                                 }                       
           
                                                 // main function                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
           
                                                 int                                     a[] = { -                                     1                                     , -                                     1                                     , -                                     2                                     ,                                     4                                     ,                                     3                                     };                       
                                                 int                                     n =                                     5                                     ;                       
           
                                                 System.out.println(minProductSubset(a, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Arnab Kundu.                       

Python3

                         # Python3 program to find maximum                       
                         # product of a subset.                       
           
                         # def to find maximum                       
                         # product of a subset                       
           
           
                         def                                     minProductSubset(a, n):                       
                                                 if                                     (n                                     =                                     =                                     1                                     ):                       
                                                 return                                     a[                                     0                                     ]                       
           
                                                 # Find count of negative numbers,                       
                                                 # count of zeros, maximum valued                       
                                                 # negative number, minimum valued                       
                                                 # positive number and product                       
                                                 # of non-zero numbers                       
                                                 max_neg                                     =                                     float                                     (                                     '-inf'                                     )                       
                                                 min_pos                                     =                                     float                                     (                                     'inf'                                     )                       
                                                 count_neg                                     =                                     0                       
                                                 count_zero                                     =                                     0                       
                                                 prod                                     =                                     1                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n):                       
           
                                                 # If number is 0, we don't                       
                                                 # multiply it with product.                       
                                                 if                                     (a[i]                                     =                                     =                                     0                                     ):                       
                                                 count_zero                                     =                                     count_zero                                     +                                     1                       
                                                 continue                       
           
                                                 # Count negatives and keep                       
                                                 # track of maximum valued                       
                                                 # negative.                       
                                                 if                                     (a[i] <                                     0                                     ):                       
                                                 count_neg                                     =                                     count_neg                                     +                                     1                       
                                                 max_neg                                     =                                     max                                     (max_neg, a[i])                       
           
                                                 # Track minimum positive                       
                                                 # number of array                       
                                                 if                                     (a[i] >                                     0                                     ):                       
                                                 min_pos                                     =                                     min                                     (min_pos, a[i])                       
           
                                                 prod                                     =                                     prod                                     *                                     a[i]                       
           
                                                 # If there are all zeros                       
                                                 # or no negative number                       
                                                 # present                       
                                                 if                                     (count_zero                                     =                                     =                                     n                                     or                                     (count_neg                                     =                                     =                                     0                       
                                                 and                                     count_zero >                                     0                                     )):                       
                                                 return                                     0                       
           
                                                 # If there are all positive                       
                                                 if                                     (count_neg                                     =                                     =                                     0                                     ):                       
                                                 return                                     min_pos                       
           
                                                 # If there are even number of                       
                                                 # negative numbers and count_neg                       
                                                 # not 0                       
                                                 if                                     ((count_neg &                                     1                                     )                                     =                                     =                                     0                                     and                       
                                                 count_neg !                                     =                                     0                                     ):                       
           
                                                 # Otherwise result is product of                       
                                                 # all non-zeros divided by                       
                                                 # maximum valued negative.                       
                                                 prod                                     =                                     int                                     (prod                                     /                                     max_neg)                       
           
                                                 return                                     prod                       
           
           
                         # Driver code                       
                         a                                     =                                     [                                     -                                     1                                     ,                                     -                                     1                                     ,                                     -                                     2                                     ,                                     4                                     ,                                     3                                     ]                       
                         n                                     =                                     len                                     (a)                       
                         print                                     (minProductSubset(a, n))                       
                         # This code is contributed by                       
                         # Manish Shaw (manishshaw1)                       

C#

                         // C# program to find maximum product of                       
                         // a subset.                       
                         using                                     System;                       
           
                         public                                     class                                     GFG {                       
           
                                                 static                                     int                                     minProductSubset(                                     int                                     [] a,                                     int                                     n)                       
                                                 {                       
                                                 if                                     (n == 1)                       
                                                 return                                     a[0];                       
           
                                                 // Find count of negative numbers,                       
                                                 // count of zeros, maximum valued                       
                                                 // negative number, minimum valued                       
                                                 // positive number and product of                       
                                                 // non-zero numbers                       
                                                 int                                     negmax =                                     int                                     .MinValue;                       
                                                 int                                     posmin =                                     int                                     .MinValue;                       
                                                 int                                     count_neg = 0, count_zero = 0;                       
                                                 int                                     product = 1;                       
           
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
           
                                                 // if number is zero, count it                       
                                                 // but dont multiply                       
                                                 if                                     (a[i] == 0) {                       
                                                 count_zero++;                       
                                                 continue                                     ;                       
                                                 }                       
           
                                                 // count the negative numbers                       
                                                 // and find the max negative number                       
                                                 if                                     (a[i] < 0) {                       
                                                 count_neg++;                       
                                                 negmax = Math.Max(negmax, a[i]);                       
                                                 }                       
           
                                                 // find the minimum positive number                       
                                                 if                                     (a[i] > 0 && a[i] < posmin) {                       
                                                 posmin = a[i];                       
                                                 }                       
           
                                                 product *= a[i];                       
                                                 }                       
           
                                                 // if there are all zeroes                       
                                                 // or zero is present but no                       
                                                 // negative number is present                       
                                                 if                                     (count_zero == n                       
                                                 || (count_neg == 0 && count_zero > 0))                       
                                                 return                                     0;                       
           
                                                 // If there are all positive                       
                                                 if                                     (count_neg == 0)                       
                                                 return                                     posmin;                       
           
                                                 // If there are even number except                       
                                                 // zero of negative numbers                       
                                                 if                                     (count_neg % 2 == 0 && count_neg != 0) {                       
           
                                                 // Otherwise result is product of                       
                                                 // all non-zeros divided by maximum                       
                                                 // valued negative.                       
                                                 product = product / negmax;                       
                                                 }                       
           
                                                 return                                     product;                       
                                                 }                       
           
                                                 // main function                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
           
                                                 int                                     [] a =                                     new                                     int                                     [] { -1, -1, -2, 4, 3 };                       
                                                 int                                     n = 5;                       
           
                                                 Console.WriteLine(minProductSubset(a, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Ajit.                       

PHP

                         <?php                       
                         // PHP program to find maximum                       
                         // product of a subset.                       
           
                         // Function to find maximum                       
                         // product of a subset                       
                         function                                     minProductSubset(                                     $a                                     ,                                     $n                                     )                       
                         {                       
                                   
                                                 if                                     (                                     $n                                     == 1)                       
                                                 return                                     $a                                     [0];                       
           
                                                 // Find count of negative numbers,                       
                                                 // count of zeros, maximum valued                       
                                                 // negative number, minimum valued                       
                                                 // positive number and product                       
                                                 // of non-zero numbers                       
                                                 $max_neg                                     = PHP_INT_MIN;                       
                                                 $min_pos                                     = PHP_INT_MAX;                       
                                                 $count_neg                                     = 0;                                     $count_zero                                     = 0;                       
                                                 $prod                                     = 1;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
           
                                                 // If number is 0, we don't                       
                                                 // multiply it with product.                       
                                                 if                                     (                                     $a                                     [                                     $i                                     ] == 0)                       
                                                 {                       
                                                 $count_zero                                     ++;                       
                                                 continue                                     ;                       
                                                 }                       
           
                                                 // Count negatives and keep                       
                                                 // track of maximum valued                       
                                                 // negative.                       
                                                 if                                     (                                     $a                                     [                                     $i                                     ] < 0)                       
                                                 {                       
                                                 $count_neg                                     ++;                       
                                                 $max_neg                                     = max(                                     $max_neg                                     ,                                     $a                                     [                                     $i                                     ]);                       
                                                 }                       
           
                                                 // Track minimum positive                       
                                                 // number of array                       
                                                 if                                     (                                     $a                                     [                                     $i                                     ] > 0)                       
                                                 $min_pos                                     = min(                                     $min_pos                                     ,                                     $a                                     [                                     $i                                     ]);                       
           
                                                 $prod                                     =                                     $prod                                     *                                     $a                                     [                                     $i                                     ];                       
                                                 }                       
           
                                                 // If there are all zeros                       
                                                 // or no negative number                       
                                                 // present                       
                                                 if                                     (                                     $count_zero                                     ==                                     $n                                     ||                       
                                                 (                                     $count_neg                                     == 0 &&                       
                                                 $count_zero                                     > 0))                       
                                                 return                                     0;                       
           
                                                 // If there are all positive                       
                                                 if                                     (                                     $count_neg                                     == 0)                       
                                                 return                                     $min_pos                                     ;                       
           
                                                 // If there are even number of                       
                                                 // negative numbers and count_neg                       
                                                 // not 0                       
                                                 if                                     (!(                                     $count_neg                                     & 1) &&                       
                                                 $count_neg                                     != 0)                       
                                                 {                       
           
                                                 // Otherwise result is product of                       
                                                 // all non-zeros divided by maximum                       
                                                 // valued negative.                       
                                                 $prod                                     =                                     $prod                                     /                                     $max_neg                                     ;                       
                                                 }                       
           
                                                 return                                     $prod                                     ;                       
                         }                       
           
                         // Driver code                       
                         $a                                     =                                     array                                     ( -1, -1, -2, 4, 3 );                       
                         $n                                     = sizeof(                                     $a                                     );                       
                         echo                                     (minProductSubset(                                     $a                                     ,                                     $n                                     ));                       
           
                         // This code is contributed by Ajit.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to find maximum                       
                         // product of a subset.                       
                         function                                     minProductSubset(a, n)                       
                         {                       
                                                 if                                     (n == 1)                       
                                                 return                                     a[0];                       
           
                                                 // Find count of negative numbers,                       
                                                 // count of zeros, maximum valued                       
                                                 // negative number, minimum valued                       
                                                 // positive number and product of                       
                                                 // non-zero numbers                       
                                                 let negmax = Number.MIN_VALUE;                       
                                                 let posmin = Number.MIN_VALUE;                       
                                                 let count_neg = 0, count_zero = 0;                       
                                                 let product = 1;                       
           
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                   
                                                 // If number is zero, count it                       
                                                 // but dont multiply                       
                                                 if                                     (a[i] == 0)                       
                                                 {                       
                                                 count_zero++;                       
                                                 continue                                     ;                       
                                                 }                       
           
                                                 // Count the negative numbers                       
                                                 // and find the max negative number                       
                                                 if                                     (a[i] < 0)                       
                                                 {                       
                                                 count_neg++;                       
                                                 negmax = Math.max(negmax, a[i]);                       
                                                 }                       
           
                                                 // Find the minimum positive number                       
                                                 if                                     (a[i] > 0 && a[i] < posmin)                       
                                                 {                       
                                                 posmin = a[i];                       
                                                 }                       
           
                                                 product *= a[i];                       
                                                 }                       
           
                                                 // If there are all zeroes                       
                                                 // or zero is present but no                       
                                                 // negative number is present                       
                                                 if                                     (count_zero == n || (count_neg == 0 &&                       
                                                 count_zero > 0))                       
                                                 return                                     0;                       
           
                                                 // If there are all positive                       
                                                 if                                     (count_neg == 0)                       
                                                 return                                     posmin;                       
           
                                                 // If there are even number except                       
                                                 // zero of negative numbers                       
                                                 if                                     (count_neg % 2 == 0 && count_neg != 0)                       
                                                 {                       
           
                                                 // Otherwise result is product of                       
                                                 // all non-zeros divided by maximum                       
                                                 // valued negative.                       
                                                 product = parseInt(product / negmax, 10);                       
                                                 }                       
                                                 return                                     product;                       
                         }                       
           
                         // Driver code                       
                         let a = [ -1, -1, -2, 4, 3 ];                       
                         let n = 5;                       
           
                         document.write(minProductSubset(a, n));                       
           
                         // This code is contributed by rameshtravel07                       
           
                         </script>                       

输出：

-24

时间复杂性： O（n） 辅助空间： O（1）

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章