# Maximum Product Subset of an array

#### Algorithms Greedy Algorithms

Get FREE domain for 1st year and build your brand new site

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:

1. Generate all subsets of the array.
2. Calculate the product of all the elements over the subset.
3. 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:

1. 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.
2. If there are an even number of negative numbers, the result is the product of all non-zero numbers.
3. If there are zeros and no positive numbers, the result is zero.
4. 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.