Max Product Subset

Time: O(n)

Space: O(1)

Intuition

The product is maximized by using all non-zero values except one negative when negatives are odd. If negatives are odd, excluding the negative with the smallest absolute value loses the least magnitude. Zeros are ignored unless they are needed to avoid returning a negative product in edge cases.

Algorithm

1Count positive, negative, and zero elements while tracking minimum absolute negative value.
2If all elements are zero, return 0.
3If there is exactly one negative and all others are zero, return 0.
4Multiply absolute values of all non-zero numbers modulo 1e9+7.
5If negative count is odd, skip exactly one occurrence of the minimum-absolute negative.
6Return the computed product.

Example Walkthrough

Input: arr = [-1, -1, -2, 4, 3]

1.negatives = 3 (odd), positives = 2, zeros = 0.
2.Minimum absolute negative is 1, so skip one -1.
3.Multiply remaining absolute values: 1 * 2 * 4 * 3 = 24.

Output: 24

Common Pitfalls

•Skipping a different negative than the minimum-absolute one reduces the product.
•Including zeros in multiplication collapses result to 0 incorrectly.
•Edge case with one negative and only zeros must return 0.

Max Product Subset.java

Java


// Approach: Include all positives and negatives (even count) to maximise product.
// If negCount is odd, exclude the negative with the smallest absolute value.
// Special case: if only one negative and no positives, return 0 (if zeros exist) or that negative.
// All zeros → return 0. Use absolute values during product computation; result is always positive.
// Time: O(n) Space: O(1)
class Solution {

    public int findMaxProduct(int[] arr) {
        final int MOD = (int) 1e9 + 7;

        int negCount = 0, posCount = 0, zeroCount = 0;
        int minAbsNeg = Integer.MAX_VALUE;

        for (int x : arr) {
            if (x > 0) {
                posCount++; 
            }else if (x < 0) {
                negCount++;
                minAbsNeg = Math.min(minAbsNeg, -x);
            } else {
                zeroCount++;
            }
        }

        // All zeros — no positive product possible
        if (negCount == 0 && posCount == 0) {
            return 0;
        }

        // One negative, no positives: best subset is {0} if a zero exists, else the negative itself
        if (negCount == 1 && posCount == 0) {
            if (zeroCount > 0) {
                return 0;
            }
            for (int x : arr) {
                if (x < 0) {
                    return x;
                }
            }
        }

        // Multiply absolute values of all non-zeros, skipping one negative (minAbsNeg) if negCount is odd
        boolean skipped = false;
        long pro = 1;
        for (int x : arr) {
            if (x == 0) {
                continue;
            }
            if (!skipped && negCount % 2 == 1 && x < 0 && -x == minAbsNeg) {
                skipped = true;
                continue;
            }
            pro = pro * Math.abs(x) % MOD;
        }

        return (int) pro;
    }
}

Was this solution helpful?