Maximum and Minimum Product Subsets - GeeksforGeeks
Given a set, we need to find maximum and minimum possible product among all subsets of the set.
As array can have negative value, zero and positive value, this problem can have lot of edge cases, if not attacked properly. Below given solution maintains maximum product and minimum product at current index and previous index and at any instant current product takes value from previous max or previous min multiplied with current element, depending on the sign of current element. For example, if we are finding maximum product then current maximum will be previous max times current value if current element is positive otherwise previous min times current value if current element is negative. Same procedure is applied for finding minimum product also.
http://www.techiedelight.com/maximum-product-subset-problem/
Read full article from Maximum and Minimum Product Subsets - GeeksforGeeks
Given a set, we need to find maximum and minimum possible product among all subsets of the set.
As array can have negative value, zero and positive value, this problem can have lot of edge cases, if not attacked properly. Below given solution maintains maximum product and minimum product at current index and previous index and at any instant current product takes value from previous max or previous min multiplied with current element, depending on the sign of current element. For example, if we are finding maximum product then current maximum will be previous max times current value if current element is positive otherwise previous min times current value if current element is negative. Same procedure is applied for finding minimum product also.
pair<int, int> getMaxandMinProduct(int arr[], int n){ // Initialize all products with arr[0] int curMaxProduct = arr[0]; int curMinProduct = arr[0]; int prevMaxProduct = arr[0]; int prevMinProduct = arr[0]; int maxProduct = arr[0]; int minProduct = arr[0]; // Process all elements after arr[0] for (int i = 1; i < n; ++i) { /* Current maximum product is maximum of following 1) prevMax * curelement (when curelement is +ve) 2) prevMin * curelement (when curelement is -ve) 3) Element itself 4) Previous max product */ curMaxProduct = max(prevMaxProduct * arr[i], max(prevMinProduct * arr[i], arr[i])); curMaxProduct = max(curMaxProduct, prevMaxProduct); /* Current min product computation is Similar to that of current max profuct */ curMinProduct = min(prevMaxProduct * arr[i], min(prevMinProduct * arr[i], arr[i])); curMinProduct = min(curMinProduct, prevMinProduct); maxProduct = max(maxProduct, curMaxProduct); minProduct = min(minProduct, curMinProduct); // copy current values to previous values prevMaxProduct = curMaxProduct; prevMinProduct = curMinProduct; } return make_pair(minProduct, maxProduct);}http://www.techiedelight.com/maximum-product-subset-problem/
Given an array of integers, find a subset in it that has maximum product of its elements.
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.
// Function to generate the product of all elements in the given set
// and update maximum product found so far
void maxProduct(vector<int> const set, int &maximum)
{
int product = 1;
for (int j : set)
product = product * j;
// if the set is not empty, then update the product
if (set.size())
maximum = max (maximum, product);
}
// Function to generate power set of given set S
void findPowerSet(vector<int> const &S, vector<int> &set, int n, int &maximum)
{
// if we have considered all elements, we have generated a subset
if (n == 0)
{
// compute its product of elements & update maximum product found so far
maxProduct(set, maximum);
return;
}
// consider nth element
set.push_back(S[n - 1]);
findPowerSet(S, set, n - 1, maximum);
// or don't consider nth element
set.pop_back();
findPowerSet(S, set, n - 1, maximum);
}
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.
int maxProduct(int arr[], int n)
{
// base case
if (n == 0)
return 0;
// if array contains only one element
if (n == 1)
return arr[0];
int product = 1; // to store maximum product subset
// stores the negative element having minimum absolute value in the set
int abs_min_so_far = INT_MAX;
int negative = 0; // maintain count of negative elements in the set
int positive = 0; // maintain count of positive elements in the set
int contains_zero = 0;
// traverse the given array
for (int i = 0; i < n; i++)
{
// if current element is negative
if (arr[i] < 0)
{
negative++;
abs_min_so_far = min(abs_min_so_far, abs(arr[i]));
}
// if current element is positive
else if (arr[i] > 0)
{
positive++;
}
// if current element is zero
if (arr[i] == 0)
contains_zero = 1;
else
product = product * arr[i];
}
// if odd number of negative elements are present, exclude the negative
// element having minimum absolute value from the subset
if (negative & 1)
product = product / -abs_min_so_far;
// special case - set contains one negative element and one or more zeroes
if (negative == 1 && !positive && contains_zero)
product = 0;
// return maximum product
return product;
}
