# Maximum Product Subset of an array

Reading time: 20 minutes

For a given array of elements, we have to find the non-empty subset having the **maximum product**. We will explore two techniques:

- brute force O(2^N)
- Greedy algorithm O(N)

## Example

Given an array { 1, -1, 2, 0, -10, -2}

The subset {1, 2, -10, -2} will have the maximum product that is 40.

All other subsets will have product less than 40.

## Naive Approach `O(2^N)`

A naive approach would be to generate all subsets of the array of length **N** and calculating the product for each of them. Since generating all subsets takes exponential time, this approach is very inefficient.

The steps involved are:

- Generate all subsets of the array.
- Calculate the product of all the elements over the subset.
- Update the maximum value of the product.

**Pseudocode:**

```
Input: Set[], set_size
1. Get the size of power set
powet_set_size = pow(2, set_size)
max_product = INT_MIN
2 Loop for counter from 0 to pow_set_size
(a) Loop for i = 0 to set_size
(i) Initialize product_temp to 1
(ii) If ith bit in counter is set
Print ith element from set for this subset
Update product_temp by multiplying with ith element
(iii) Set max_product to max(max_product, product_temp)
(b) Print seperator for subsets i.e., newline
```

### Algorithm `O(N)`

We can come up with a better solution if we pay attention to the following:

- If there are an odd number of negative numbers, the result is the product of all non-zero numbers except the largest valued negative number.
- If there are an even number of negative numbers, the result is the product of all non-zero numbers.
- If there are zeros and no positive numbers, the result is zero.
- If all numbers are negative, the result is the largest valued number

### Implementation

```
#include <bits/stdc++.h>
using namespace std;
int main()
{
//Taking input of size of array of numbers
int n;
cin >> n;
//Declaring a vector to store the numbers
vector<int> a(n);
//Setting variable negative to store maximum valued negative number
int negative = INT_MIN;
//Counter variables to store number of zeros and negative numbers
int countzero = 0, countneg = 0;
//Initializing product to 1
int product = 1;
for(int i=0;i<n;i++){
//Taking input of elements
cin >> a[i];
if(a[i]==0){
//Incrementing zero counter if input is 0
countzero++;
}else if(a[i]<0){
//Incrementing negative counter if input is <0
countneg++;
//Updating negative to maximum valued negative number
negative = max(negative, a[i]);
}
//Updating product
product *= a[i];
}
if(countzero==n){
// If there are all zeros
cout << 0;
}else if(countneg%2){
// If there are odd number of negative numbers
if(countneg==1 && countzero>0 && countzero+countneg==n) {
//If there is only one negative number and all others are zeros
cout << 0;
}else {
//Result is product of all non-zeros divided by maximum valued negative.
cout << product / negative;
}
}else{
cout << product;
}
return 0;
}
```

### Examples

Consider the following arrays:

- For the following array, the maximum product is the product of all numbers except maximum valued negative number, i.e., 432({-4,-6,3,6}):
- For the following array, the maximum product is the maximum number, i.e., 0:
- For the following array, the maximum product is product of all non-zero numbers, i.e., 2:
- For the following array, the maximum product is the product of all, i.e., 126 ({2, 7, 9}):
- For the following array, the maximum product is the product of all numbers, i.e., 864 ({4, -6, -2, 3, 6}):

### Complexity

The time complexity of this algorithm is `O(N)`

, as the array is traversed only once.