Maximum Product Subset Problem

Given an array of integers, find a subset in it that has maximum product of its elements.

 

For example,

 


Input:  A[] = { -6, 4, -5, 8, -10, 0, 8 }

Output: The maximum product of a subset is 15360

Explanation: The subset having maximum product of its elements is { -6, 4, 8, -10, 8 }
 
 

Input:  A[] = { 4, -8, 0, 8 }

Output: The maximum product of a subset is 32

Explanation: The subset having maximum product of its elements is { 4, 8 }

 

1. Naive Approach

 

Naive solution would be to consider every subset and find product of their elements. Finally, we return the maximum product found among all subset. The implementation can be seen below.

 
C++ implementation –
 

Download   Run Code

Output:

The maximum product of a subset is 15360

 

2. Linear time solution

 

The time complexity of above solution is exponential. We can solve this problem in linear time by finding a negative element in the set that has minimum absolute value. We also count the number of negative elements present in the set. If the count of negative elements is odd, then we exclude that negative element (having minimum absolute value) from the subset, else we consider it (since multiplication of two negative numbers will give a positive number as output). One more special case we need to handle is that 0 will never be part of subset if at-least one positive element or two negative elements are present in the subset. Rest all elements will form part of the subset.

 
C implementation –
 

Download   Run Code

Output:

The maximum product of a subset is 15360

 

The time complexity of above solution is O(n) and no extra space is used by the program.
 

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz