Maximum product subset of an array

JavaView on GFG

Time: O(n)

Space: O(1)

Problem Overview

Find maximum product of any subset.

See our study guide for structured GFG and LeetCode practice.

Intuition

Find maximum product of any subset. Handle negatives and zeros carefully.

Algorithm

1Count negatives and zeros. If all zeros: return 0. Remove zeros. If odd number of negatives: remove the negative closest to 0.
2Multiply remaining elements.

Common Pitfalls

• Handle: all zeros, single element, odd count of negatives. Sort to easily identify smallest-magnitude negative.

Maximum product subset of an array.java

Java

// Approach: Handle negatives carefully: if odd count of negatives, exclude the one with smallest absolute value.
// Time: O(n) Space: O(1)
import java.util.*;

class Solution {
    public long findMaxProduct(List<Integer> arr) {
        long pro = 1, min = Integer.MAX_VALUE;
        boolean hasZero = false, hasPositive = false;
        int mod = (int) 1e9 + 7;

        if (arr.size() == 1)
            return arr.get(0);

        for (int i = 0; i < arr.size(); i++) {
            int num = arr.get(i);
            if (num == 0) {
                hasZero = true;
                continue;
            } else if (num < 0) {
                if (Math.abs(num) < Math.abs(min))
                    min = num;

                pro *= num;
                pro %= mod;
            } else {
                hasPositive = true;
                pro *= num;
                pro %= mod;
            }
        }

        if (arr.size() == 2) {
            if (hasZero)
                return 0;
        }

        if (pro < 0)
            pro /= min;

        return pro % mod;
    }
}

Was this solution helpful?