Dada una array a, tenemos que encontrar el máximo producto posible con el subconjunto de elementos presentes en la array. El producto máximo también puede ser de un solo elemento.
Ejemplos:
Input: a[] = { -1, -1, -2, 4, 3 }
Output: 24
Explanation : Maximum product will be ( -2 * -1 * 4 * 3 ) = 24
Input: a[] = { -1, 0 }
Output: 0
Explanation: 0(single element) is maximum product possible
Input: a[] = { 0, 0, 0 }
Output: 0
Una solución simple es generar todos los subconjuntos , encontrar el producto de cada subconjunto y devolver el producto máximo.
Una mejor solución es usar los siguientes datos.
- Si hay un número par de números negativos y ningún cero, el resultado es simplemente el producto de todos
- Si hay un número impar de números negativos y ningún cero, el resultado es el producto de todos excepto el entero negativo con el menor valor absoluto.
- Si hay ceros, el resultado es el producto de todos excepto estos ceros con un caso excepcional. El caso excepcional es cuando hay un número negativo y todos los demás elementos son 0. En este caso, el resultado es 0.
A continuación se muestra la implementación del enfoque anterior:
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;
}
C
// C program to find maximum product of
// a subset.
#include <stdio.h>
#include<math.h>
#include<stdlib.h>
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 = -100000009;
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 = fmax(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]);
printf("%d",maxProductSubset(a, n));
return 0;
}
// This code is contributed by rexomkar.
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>
Producción
24
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Surya Priy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA