# Maximum Product Subset Problem

Posted in

Vinay Khatri
Last updated on September 10, 2024

## Problem

Given array a, we have to find the maximum product possible with the subset of elements present in the array.

#### Sample Input

`[1, -2, 4, 4]`

`16`

#### Explanation

4 x 4 x 1 = 16

## Approach

If there are even numbers that are negative and no zero is present, then the outcome is just the product of all numbers because we will require all elements. If there's an odd number of negatives and no zeros, take the product of all except the negative integer with the least absolute value as the product of the result.

If there are zeros, the result is the product of all except these zeros with one exceptional case: when there is one negative number and all other elements are 0, then the answer is 0.

### C++ Programming

```#include <bits/stdc++.h>
using namespace std;
//function to get maximum subset
int solve(int a[], int n)
{
if (n == 1)
return a[0];
int maxNeg = INT_MIN;
int countNeg = 0, count_zero = 0;
int ans = 1;
for (int i = 0; i < n; i++) {
// If number is 0, we don't consider it
if (a[i] == 0)
{
count_zero++;
continue;
}
if (a[i] < 0)
{
countNeg++;
maxNeg = max(maxNeg, a[i]);
}

ans = ans * a[i];
}

if (count_zero == n)
return 0;

// If there are odd number of
// negatives
if (countNeg & 1)
{
// Exceptional case: There is only one negative and all other are zeros
if (countNeg == 1 && count_zero > 0 && count_zero + countNeg == n)
return 0;
ans = ans / maxNeg;
}

return ans;
}

int main()
{
int a[] = { -1, 4, 4, 1};
int n = sizeof(a) / sizeof(a[0]);
cout << solve(a, n);
return 0;
}```

Output

`16`

### C Programming

```#include<stdio.h>
#define INT_MIN -1000000000
//function to get maximum subset
int max(int a, int b)
{
return a>=b?a:b;
}
int solve(int a[], int n)
{
if (n == 1)
return a[0];
int maxNeg = INT_MIN;   //declare minimum possible value
int countNeg = 0, count_zero = 0;
int ans = 1;
for (int i = 0; i < n; i++)
{
// If number is 0, we don't consider it
if (a[i] == 0)
{
count_zero++;
continue;
}
if (a[i] < 0)
{
countNeg++;
maxNeg = max(maxNeg, a[i]);
}

ans = ans * a[i];
}

if (count_zero == n)
return 0;

// If there are odd number of
// negatives
if (countNeg & 1)
{
// Exceptional case: There is only one negative and all other are zeros
if (countNeg == 1 && count_zero > 0 && count_zero + countNeg == n)
return 0;
ans = ans / maxNeg;
}
return ans;
}

int main()
{
int a[] = { -1, 4, 4, 1};
int n = sizeof(a) / sizeof(a[0]);
printf("%d",solve(a, n));
return 0;
}
```

Output

`16`

### Python Programming

```def solve(a, n):
if n == 1:
return a[0]

maxNeg = -999999999999
countNeg = 0
countZero = 0
ans = 1

for i in range(n):
if a[i] == 0:
countZero += 1
continue

if a[i] < 0:
countNeg += 1
maxNeg = max(maxNeg, a[i])
ans = ans * a[i]

if countZero == n:
return 0

if countNeg & 1:
if (countNeg == 1 and countZero > 0 and
countZero + countNeg == n):
return 0

ans = int(ans / maxNeg)
return ans

if __name__ == '__main__':
a = [ -1, 4, 4, 1]
n = len(a)
print(solve(a, n))```

Output

`16`

People are also reading: