Maximum Product Subset - C++ Solution

1. Introduction

This blog post explores a problem related to finding the maximum product of elements among all subsets of an integer array. This problem is an example of dynamic programming and optimization strategies in array processing.

Problem

Given an integer array, the task is to find the maximum product that can be obtained from the elements of any of its subsets. This includes considering subsets with negative and zero values, and empty subsets.

2. Solution Steps

1. Handle edge cases such as an empty array and an array with only one element.

2. Initialize variables for the maximum product, count of negative numbers, largest negative number, and product excluding zero values.

3. Iterate through the array, updating these variables accordingly.

4. Calculate the maximum product based on the number of negative elements and whether zeros are present.

5. Return the maximum product.

3. Code Program

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxProductSubset(const vector<int>& nums) {
    if (nums.empty()) return 0;

    int maxProduct = 1;
    int negativeCount = 0, maxNegative = INT_MIN, zeroCount = 0;

    for (int num : nums) {
        if (num == 0) {
            zeroCount++;
            continue;
        }

        if (num < 0) {
            negativeCount++;
            maxNegative = max(maxNegative, num);
        }

        maxProduct *= num;
    }

    if (zeroCount == nums.size()) return 0;

    if (negativeCount % 2 != 0) {
        if (negativeCount == 1 && zeroCount + negativeCount == nums.size()) {
            return 0;
        }
        maxProduct /= maxNegative;
    }

    return maxProduct;
}

int main() {
    vector<int> nums = {-6, 4, -5, 8, -10, 0, 8};
    cout << "Maximum Product: " << maxProductSubset(nums) << endl;
    return 0;
}

Output:

Maximum Product: 15360

Explanation:

The function maxProductSubset calculates the maximum product of any subset of the given array. It handles special cases like an empty array and arrays containing zeros. The function counts the number of negative numbers and tracks the largest negative number to decide whether to include it in the product. For the input array [-6, 4, -5, 8, -10, 0, 8], the subset with the maximum product is [-6, 4, 8, -10, 8], giving a product of 15360.