141. Maximum Product Subset of an Array

Given an array of n integers (which may include negatives and zeros), find the maximum product achievable by any non-empty subset of its elements.

Input: The first line contains an integer n. The second line contains n space-separated integers, which may include negative numbers and zeros. Output: Print a single integer - the maximum product achievable by any non-empty subset.

1 <= n <= 10^5

Zeros are simply IGNORED in this greedy approach (never included, since including one would zero out the whole product) UNLESS the entire array is zeros, in which case 0 is unavoidably the answer, per the special case.

Find the maximum product achievable from a non-empty subset of an array that may contain negatives and zeros. Brute force: Try every possible non-empty subset directly and compute its product - this is exponential (2^n subsets), completely impractical for large n. Optimised: Since every positive number always helps and every PAIR of negative numbers also helps (two negatives multiply to a positive), the only real decision is what to do with a LEFTOVER unpaired negative number (drop the least damaging one, closest to zero) - this direct classification-based approach avoids ever needing to try subset combinations explicitly.

Enumerate every non-empty subset of the array (there are 2^n - 1 of them), compute the product of each subset's elements, and keep track of the largest product seen. This is a direct exhaustive search that is guaranteed correct but grows exponentially with array size. Time: O(2^n) Space: O(1)

Sort the array first, which makes it trivial to separate it into a contiguous run of negatives, a possible zero region, and a run of positives, and to identify the negative closest to zero (the largest, i.e. last, negative in sorted order). Multiply together all non-zero elements; if the count of negatives is odd, divide out (exclude) that largest negative to flip the sign back to positive, since removing the negative closest to zero loses the least magnitude. Sorting makes identifying that specific negative and the array structure a simple positional lookup rather than a separate scan. Time: O(n log n) Space: O(1) extra (in-place sort) or O(n)

Make one linear pass over the array, simultaneously counting negatives, counting zeros, computing the running product of all non-zero elements, and tracking the maximum-valued (closest-to-zero) negative encountered. Apply the same rule as before, excluding that tracked negative if the negative count is odd, and handling the edge cases where the whole array is zero (answer 0) or is a single negative with nothing else to pair it with (must include it, answer is that value). This produces the identical result as the sort-based approach without ever needing to sort, cutting the time to linear. Time: O(n) Space: O(1)

1. Take every POSITIVE number - they always help the product. 2. Among the NEGATIVE numbers: if there's an EVEN count of them, take all of them (their combined product is positive); if ODD, drop the negative number CLOSEST TO ZERO (smallest absolute value) to make the count even, keeping the rest. 3. Special-case: an all-zero array gives answer 0; an array with no positives and exactly one negative gives that single negative number as the answer.

Time: O(n log n) if sorting is used to find the negative closest to zero, or O(n) with a single pass tracking the needed values directly. Space: O(1) extra space beyond a few running trackers.

n = 1, an array of all zeros (answer 0), an array with no positive numbers and exactly one negative number (answer is that negative number), and an odd count of negative numbers forcing one to be dropped.

Be ready to handle the special edge cases explicitly (all zeros, single negative with no positives) - these are the most common places a first attempt at this problem goes wrong.