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:

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.