Maximum Product Subset Problem

Problem

Given array a, we have to find the maximum product possible with the subset of elements present in the array.

Sample Input

[1, -2, 4, 4]

Sample Output

16

Explanation

4 x 4 x 1 = 16

Approach

If there are even numbers that are negative and no zero is present, then the outcome is just the product of all numbers because we will require all elements. If there's an odd number of negatives and no zeros, take the product of all except the negative integer with the least absolute value as the product of the result.

If there are zeros, the result is the product of all except these zeros with one exceptional case: when there is one negative number and all other elements are 0, then the answer is 0.

C++ Programming

#include <bits/stdc++.h>
using namespace std;
//function to get maximum subset
int solve(int a[], int n)
{
 if (n == 1)
    return a[0];
 int maxNeg = INT_MIN;
 int countNeg = 0, count_zero = 0;
 int ans = 1;
 for (int i = 0; i < n; i++) {
     // If number is 0, we don't consider it
     if (a[i] == 0) 
        {
        count_zero++;
         continue;
        }
     if (a[i] < 0) 
       {
         countNeg++;
         maxNeg = max(maxNeg, a[i]);
       }

      ans = ans * a[i];
 }

 if (count_zero == n)
     return 0;

 // If there are odd number of
 // negatives
 if (countNeg & 1) 
     {
      // Exceptional case: There is only one negative and all other are zeros
      if (countNeg == 1 && count_zero > 0 && count_zero + countNeg == n)
         return 0;
 ans = ans / maxNeg;
 }

 return ans;
}

int main()
{
 int a[] = { -1, 4, 4, 1};
 int n = sizeof(a) / sizeof(a[0]);
 cout << solve(a, n);
 return 0;
}

Output

16

C Programming

#include<stdio.h>
#define INT_MIN -1000000000
//function to get maximum subset
int max(int a, int b)
{
    return a>=b?a:b;
}
int solve(int a[], int n)
{
   if (n == 1)
      return a[0];
   int maxNeg = INT_MIN;   //declare minimum possible value
   int countNeg = 0, count_zero = 0;
   int ans = 1;
   for (int i = 0; i < n; i++) 
   {
     // If number is 0, we don't consider it
     if (a[i] == 0) 
      {
      count_zero++;
      continue;
      }
     if (a[i] < 0) 
     {
      countNeg++;
      maxNeg = max(maxNeg, a[i]);
     }

     ans = ans * a[i];
  }

  if (count_zero == n)
     return 0;

  // If there are odd number of
  // negatives
  if (countNeg & 1) 
    {
     // Exceptional case: There is only one negative and all other are zeros
     if (countNeg == 1 && count_zero > 0 && count_zero + countNeg == n)
        return 0;
    ans = ans / maxNeg;
     }
  return ans;
}

int main()
{
   int a[] = { -1, 4, 4, 1};
   int n = sizeof(a) / sizeof(a[0]);
   printf("%d",solve(a, n));
   return 0;
}

Output

16

Python Programming

def solve(a, n):
    if n == 1:
        return a[0]

    maxNeg = -999999999999
    countNeg = 0
    countZero = 0
    ans = 1

    for i in range(n):
        if a[i] == 0:
            countZero += 1
            continue

        if a[i] < 0:
            countNeg += 1
            maxNeg = max(maxNeg, a[i])
        ans = ans * a[i]

    if countZero == n:
        return 0

    if countNeg & 1:
        if (countNeg == 1 and countZero > 0 and
            countZero + countNeg == n):
            return 0

        ans = int(ans / maxNeg)
    return ans

if __name__ == '__main__':
    a = [ -1, 4, 4, 1]
    n = len(a)
    print(solve(a, n))

Output

16

People are also reading:

• Python Program to Calculate the Area of a Triangle
• How to Find Square Root in Python?
• Python RegEx
• How many Centimeters in a Foot through Python?
• C Program to Design Love Calculator
• Rectangle & Pyramids Pattern in C++
• C Program to Convert Feet into Inches
• Python Program to Check if a Number is Odd or Even
• C Program to Extract a Portion of String
• Python Program to Display Calendar