Maximum Product Subset Problem

Posted in

Maximum Product Subset Problem
vinaykhatri

Vinay Khatri
Last updated on May 30, 2024

    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:

    Leave a Comment on this Post

    0 Comments