Maximum product subset of an array

JavaView on GFG

Time: O(n)

Space: O(1)

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?