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

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

null

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

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

A. 简单解决方案 就是生成所有子集，找到每个子集的乘积并返回最大乘积。 A. 更好的解决方案 就是使用以下事实。

如果有偶数个负数而没有零，结果就是所有的乘积
如果有奇数个负数且没有零，则结果是除绝对值最小的负整数外的所有负数的乘积。
如果有零，结果是除这些零之外的所有零与一个例外情况的乘积。例外情况是当有一个负数，而所有其他元素都为0时。在本例中，结果为0。

以下是上述方法的实施情况：

C++

                         // CPP program to find maximum product of                       
                         // a subset.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         int                                     maxProductSubset(                                     int                                     a[],                                     int                                     n)                       
                         {                       
                                                 if                                     (n == 1)                       
                                                 return                                     a[0];                       
           
                                                 // Find count of negative numbers, count                       
                                                 // of zeros, negative number                       
                                                 // with least absolute value                       
                                                 // and product of non-zero numbers                       
                                                 int                                     max_neg = INT_MIN;                       
                                                 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 negative number                       
                                                 // with least absolute value                       
                                                 if                                     (a[i] < 0) {                       
                                                 count_neg++;                       
                                                 max_neg = max(max_neg, a[i]);                       
                                                 }                       
           
                                                 prod = prod * a[i];                       
                                                 }                       
           
                                                 // If there are all zeros                       
                                                 if                                     (count_zero == n)                       
                                                 return                                     0;                       
           
                                                 // If there are odd number of                       
                                                 // negative numbers                       
                                                 if                                     (count_neg & 1) {                       
           
                                                 // Exceptional case: There is only                       
                                                 // negative and all other are zeros                       
                                                 if                                     (count_neg == 1 &&                       
                                                 count_zero > 0 &&                       
                                                 count_zero + count_neg == n)                       
                                                 return                                     0;                       
           
                                                 // Otherwise result is product of                       
                                                 // all non-zeros divided by                       
                                                 //negative number with                       
                                                 // least absolute value                       
                                                 prod = prod / max_neg;                       
                                                 }                       
           
                                                 return                                     prod;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     a[] = {  -1, -1, -2, 4, 3  };                       
                                                 int                                     n =                                     sizeof                                     (a) /                                     sizeof                                     (a[0]);                       
                                                 cout << maxProductSubset(a, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find maximum product of                       
                         // a subset.                       
           
                         class                                     GFG {                       
           
                                                 static                                     int                                     maxProductSubset(                                     int                                     a[],                                     int                                     n) {                       
                                                 if                                     (n ==                                     1                                     ) {                       
                                                 return                                     a[                                     0                                     ];                       
                                                 }                       
           
                                                 // Find count of negative numbers, count                       
                                                 // of zeros, negative number                       
                                                 // with least absolute value                       
                                                 // and product of non-zero numbers                       
                                                 int                                     max_neg = Integer.MIN_VALUE;                       
                                                 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 negative number                       
                                                 // with least absolute value.                       
                                                 if                                     (a[i] <                                     0                                     ) {                       
                                                 count_neg++;                       
                                                 max_neg = Math.max(max_neg, a[i]);                       
                                                 }                       
           
                                                 prod = prod * a[i];                       
                                                 }                       
           
                                                 // If there are all zeros                       
                                                 if                                     (count_zero == n) {                       
                                                 return                                     0                                     ;                       
                                                 }                       
           
                                                 // If there are odd number of                       
                                                 // negative numbers                       
                                                 if                                     (count_neg %                                     2                                     ==                                     1                                     ) {                       
           
                                                 // Exceptional case: There is only                       
                                                 // negative and all other are zeros                       
                                                 if                                     (count_neg ==                                     1                       
                                                 && count_zero >                                     0                       
                                                 && count_zero + count_neg == n) {                       
                                                 return                                     0                                     ;                       
                                                 }                       
           
                                                 // Otherwise result is product of                       
                                                 // all non-zeros divided by                       
                                                 //negative number with                       
                                                 // least absolute value.                       
                                                 prod = prod / max_neg;                       
                                                 }                       
           
                                                 return                                     prod;                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     main(String[] args) {                       
                                                 int                                     a[] = {-                                     1                                     , -                                     1                                     , -                                     2                                     ,                                     4                                     ,                                     3                                     };                       
                                                 int                                     n = a.length;                       
                                                 System.out.println(maxProductSubset(a, n));                       
           
                                                 }                       
                         }                       
                         /* This JAVA code is contributed by Rajput-Ji*/                       

Python3

                         # Python3 program to find maximum product                       
                         # of a subset.                       
           
                         def                                     maxProductSubset(a, n):                       
                                                 if                                     n                                     =                                     =                                     1                                     :                       
                                                 return                                     a[                                     0                                     ]                       
           
                                                 # Find count of negative numbers, count                       
                                                 # of zeros, negative number                       
                                                 # with least absolute value                       
                                                 # and product of non-zero numbers                       
                                                 max_neg                                     =                                     -                                     999999999999                       
                                                 count_neg                                     =                                     0                       
                                                 count_zero                                     =                                     0                       
                                                 prod                                     =                                     1                       
                                                 for                                     i                                     in                                     range                                     (n):                       
           
                                                 # If number is 0, we don't                       
                                                 # multiply it with product.                       
                                                 if                                     a[i]                                     =                                     =                                     0                                     :                       
                                                 count_zero                                     +                                     =                                     1                       
                                                 continue                       
           
                                                 # Count negatives and keep                       
                                                 # track of negative number                       
                                                 # with least absolute value.                       
                                                 if                                     a[i] <                                     0                                     :                       
                                                 count_neg                                     +                                     =                                     1                       
                                                 max_neg                                     =                                     max                                     (max_neg, a[i])                       
           
                                                 prod                                     =                                     prod                                     *                                     a[i]                       
           
                                                 # If there are all zeros                       
                                                 if                                     count_zero                                     =                                     =                                     n:                       
                                                 return                                     0                       
           
                                                 # If there are odd number of                       
                                                 # negative numbers                       
                                                 if                                     count_neg &                                     1                                     :                       
           
                                                 # Exceptional case: There is only                       
                                                 # negative and all other are zeros                       
                                                 if                                     (count_neg                                     =                                     =                                     1                                     and                                     count_zero >                                     0                                     and                       
                                                 count_zero                                     +                                     count_neg                                     =                                     =                                     n):                       
                                                 return                                     0                       
           
                                                 # Otherwise result is product of                       
                                                 # all non-zeros divided                       
                                                 # by negative number                       
                                                 # with least absolute value                       
                                                 prod                                     =                                     int                                     (prod                                     /                                     max_neg)                       
           
                                                 return                                     prod                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 a                                     =                                     [                                     -                                     1                                     ,                                     -                                     1                                     ,                                     -                                     2                                     ,                                     4                                     ,                                     3                                     ]                       
                                                 n                                     =                                     len                                     (a)                       
                                                 print                                     (maxProductSubset(a, n))                       
           
                         # This code is contributed by PranchalK                       

C#

                         // C# Java program to find maximum                       
                         // product of a subset.                       
                         using                                     System;                       
                                   
                         class                                     GFG                       
                         {                       
           
                         static                                     int                                     maxProductSubset(                                     int                                     []a,                       
                                                 int                                     n)                       
                         {                       
                                                 if                                     (n == 1)                       
                                                 {                       
                                                 return                                     a[0];                       
                                                 }                       
           
                                                 // Find count of negative numbers,                       
                                                 // count of zeros, negative number with                       
                                                 // least absolute value and product of                       
                                                 // non-zero numbers                       
                                                 int                                     max_neg =                                     int                                     .MinValue;                       
                                                 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 negative number with                       
                                                 // least absolute value.                       
                                                 if                                     (a[i] < 0)                       
                                                 {                       
                                                 count_neg++;                       
                                                 max_neg = Math.Max(max_neg, a[i]);                       
                                                 }                       
           
                                                 prod = prod * a[i];                       
                                                 }                       
           
                                                 // If there are all zeros                       
                                                 if                                     (count_zero == n)                       
                                                 {                       
                                                 return                                     0;                       
                                                 }                       
           
                                                 // If there are odd number of                       
                                                 // negative numbers                       
                                                 if                                     (count_neg % 2 == 1)                       
                                                 {                       
           
                                                 // Exceptional case: There is only                       
                                                 // negative and all other are zeros                       
                                                 if                                     (count_neg == 1 && count_zero > 0 &&                       
                                                 count_zero + count_neg == n)                       
                                                 {                       
                                                 return                                     0;                       
                                                 }                       
           
                                                 // Otherwise result is product of                       
                                                 // all non-zeros divided by negative                       
                                                 // number with least absolute value.                       
                                                 prod = prod / max_neg;                       
                                                 }                       
           
                                                 return                                     prod;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main()                       
                         {                       
                                                 int                                     []a = {-1, -1, -2, 4, 3};                       
                                                 int                                     n = a.Length;                       
                                                 Console.Write(maxProductSubset(a, n));                       
                         }                       
                         }                       
           
                         // This code is contributed by Rajput-Ji                       

PHP

                         <?php                       
                         // PHP program to find maximum                       
                         // product of a subset.                       
           
                         function                                     maxProductSubset(                                     $a                                     ,                                     $n                                     )                       
                         {                       
                                                 if                                     (                                     $n                                     == 1)                       
                                                 return                                     $a                                     [0];                       
           
                                                 // Find count of negative numbers,                       
                                                 // count of zeros, negative number                       
                                                 // with least absolute value and product of                       
                                                 // non-zero numbers                       
                                                 $max_neg                                     = PHP_INT_MIN;                       
                                                 $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 negative number                       
                                                 // with least absolute value.                       
                                                 if                                     (                                     $a                                     [                                     $i                                     ] < 0)                       
                                                 {                       
                                                 $count_neg                                     ++;                       
                                                 $max_neg                                     = max(                                     $max_neg                                     ,                                     $a                                     [                                     $i                                     ]);                       
                                                 }                       
           
                                                 $prod                                     =                                     $prod                                     *                                     $a                                     [                                     $i                                     ];                       
                                                 }                       
           
                                                 // If there are all zeros                       
                                                 if                                     (                                     $count_zero                                     ==                                     $n                                     )                       
                                                 return                                     0;                       
           
                                                 // If there are odd number of                       
                                                 // negative numbers                       
                                                 if                                     (                                     $count_neg                                     & 1)                       
                                                 {                       
           
                                                 // Exceptional case: There is only                       
                                                 // negative and all other are zeros                       
                                                 if                                     (                                     $count_neg                                     == 1 &&                       
                                                 $count_zero                                     > 0 &&                       
                                                 $count_zero                                     +                                     $count_neg                                     ==                                     $n                                     )                       
                                                 return                                     0;                       
           
                                                 // Otherwise result is product of                       
                                                 // all non-zeros divided by negative                       
                                                 // number with least absolute value.                       
                                                 $prod                                     =                                     $prod                                     /                                     $max_neg                                     ;                       
                                                 }                       
           
                                                 return                                     $prod                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $a                                     =                                     array                                     (-1, -1, -2, 4, 3 );                       
                         $n                                     = sizeof(                                     $a                                     );                       
                         echo                                     maxProductSubset(                                     $a                                     ,                                     $n                                     );                       
           
                         // This code is contributed                       
                         // by Akanksha Rai                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to find maximum                       
                         // product of a subset.                       
           
                         function                                     maxProductSubset(a, n)                       
                         {                       
                                                 if                                     (n == 1)                       
                                                 return                                     a[0];                       
           
                                                 // Find count of negative numbers,                       
                                                 // count of zeros, negative number                       
                                                 // with least absolute value and product of                       
                                                 // non-zero numbers                       
                                                 let max_neg = Number.MIN_SAFE_INTEGER;                       
                                                 let count_neg = 0; count_zero = 0;                       
                                                 let prod = 1;                       
                                                 for                                     (let 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 negative number                       
                                                 // with least absolute value.                       
                                                 if                                     (a[i] < 0)                       
                                                 {                       
                                                 count_neg++;                       
                                                 max_neg = Math.max(max_neg, a[i]);                       
                                                 }                       
           
                                                 prod = prod * a[i];                       
                                                 }                       
           
                                                 // If there are all zeros                       
                                                 if                                     (count_zero == n)                       
                                                 return                                     0;                       
           
                                                 // If there are odd number of                       
                                                 // negative numbers                       
                                                 if                                     (count_neg & 1)                       
                                                 {                       
           
                                                 // Exceptional case: There is only                       
                                                 // negative and all other are zeros                       
                                                 if                                     (count_neg == 1 &&                       
                                                 count_zero > 0 &&                       
                                                 count_zero + count_neg == n)                       
                                                 return                                     0;                       
           
                                                 // Otherwise result is product of                       
                                                 // all non-zeros divided by negative                       
                                                 // number with least absolute value.                       
                                                 prod = prod / max_neg;                       
                                                 }                       
           
                                                 return                                     prod;                       
                         }                       
           
                         // Driver Code                       
                         let a = [-1, -1, -2, 4, 3 ];                       
                         let n = a.length;                       
                         document.write(maxProductSubset(a, n));                       
           
                         // This code is contributed                       
                         // by _saurabh_jaiswal                       
           
                         </script>                       

输出

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

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

THE END

技术文章