GreedyProblem 15 of 35
Maximum product subset of an array
Problem Statement
Given an array of integers, find the maximum product of a subset of the array. The subset must contain at least one element.
Constraints:
- 1 ≤ n ≤ 2 * 10^4
- -10^9 ≤ arr[i] ≤ 10^9
Example:
- Input:
arr = [3, -1, -1, 2] - Output:
6 - Explanation: Subset 2 gives product = 3 * (-1) * (-1) * 2 = 6
Example 2:
- Input:
arr = [-1, -1, -2, 4, 3] - Output:
24 - Explanation: Subset 3 or 3 gives product = 24
Example 3:
- Input:
arr = [-1, 0] - Output:
0 - Explanation: Best we can do is include 0 (single element -1 gives -1)
Approach 1: Brute Force (Try All Subsets)
Intuition
Generate all non-empty subsets and calculate product of each. Track the maximum product.
Algorithm
- Generate all 2^n - 1 non-empty subsets
- For each subset, calculate the product
- Track maximum product
java
public class Solution {
public long maxProductBrute(int[] arr) {
int n = arr.length;
long maxProduct = Long.MIN_VALUE;
for (int mask = 1; mask < (1 << n); mask++) {
long product = 1;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
product *= arr[i];
}
}
maxProduct = Math.max(maxProduct, product);
}
return maxProduct;
}
}Complexity Analysis
- Time Complexity: O(2^n * n) - 2^n subsets, O(n) per product calculation
- Space Complexity: O(1) - Only tracking current product
Approach 2: Greedy (Count Analysis) - Optimal
Intuition
Analyze the array based on:
- Count of zeros
- Count of negative numbers
- Presence of positive numbers
Key Insights:
- Product of all positive numbers should be included
- Even number of negative numbers → include all (product positive)
- Odd number of negative numbers → exclude one (the one with smallest absolute value)
- Zeros contribute nothing to product but might be the best answer if all remaining elements are single negative
Algorithm
- Count zeros, negative numbers, and track the negative with max value (smallest abs)
- Handle special cases (all zeros, single negative, etc.)
- Calculate product including all positives and pairs of negatives
- If odd negatives, exclude the one with smallest absolute value
java
import java.util.*;
public class MaxProductSubset {
public long maxProduct(int[] arr) {
int n = arr.length;
int zeroCount = 0;
int negCount = 0;
int maxNeg = Integer.MIN_VALUE;
boolean hasPositive = false;
long product = 1;
for (int num : arr) {
if (num == 0) {
zeroCount++;
} else if (num < 0) {
negCount++;
maxNeg = Math.max(maxNeg, num);
product *= num;
} else {
hasPositive = true;
product *= num;
}
}
// Special cases
if (zeroCount == n) {
return 0;
}
if (negCount == 1 && zeroCount == n - 1) {
return 0;
}
if (negCount == 1 && zeroCount == 0 && !hasPositive) {
return arr[0];
}
// If odd negatives, divide by max negative
if (negCount % 2 == 1) {
product /= maxNeg;
}
return product;
}
public List<Integer> getMaxProductSubset(int[] arr) {
int n = arr.length;
List<Integer> subset = new ArrayList<>();
int zeroCount = 0;
int negCount = 0;
int maxNegIdx = -1;
int maxNeg = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
if (arr[i] == 0) {
zeroCount++;
} else if (arr[i] < 0) {
negCount++;
if (arr[i] > maxNeg) {
maxNeg = arr[i];
maxNegIdx = i;
}
}
}
// Handle special cases
if (zeroCount == n) {
subset.add(0);
return subset;
}
if (negCount == 1 && zeroCount == n - 1) {
subset.add(0);
return subset;
}
// Include all non-zero except one negative if odd
for (int i = 0; i < n; i++) {
if (arr[i] == 0) continue;
if (negCount % 2 == 1 && i == maxNegIdx) continue;
subset.add(arr[i]);
}
if (subset.isEmpty()) {
subset.add(arr[0]);
}
return subset;
}
public static void main(String[] args) {
MaxProductSubset mps = new MaxProductSubset();
System.out.println(mps.maxProduct(new int[]{3, -1, -1, 2})); // 6
System.out.println(mps.maxProduct(new int[]{-1, -1, -2, 4, 3})); // 24
System.out.println(mps.maxProduct(new int[]{-1, 0})); // 0
System.out.println(mps.maxProduct(new int[]{-1})); // -1
}
}Dry Run Example
arr = [-1, -1, -2, 4, 3]
Categorize:
Zeros: [] (count: 0)
Negatives: [-2, -1, -1] (count: 3)
Positives: [4, 3] (count: 2)
Product of all non-zero: (-1) × (-1) × (-2) × 4 × 3 = -24
Negative count = 3 (odd)
Need to exclude one negative to make product positive.
Exclude the one with smallest absolute value = -1
Remaining negatives: [-2, -1]
Product of remaining negatives: (-2) × (-1) = 2
Total product: 2 × 4 × 3 = 24
Subset: {-2, -1, 4, 3} or equivalently {-1, -1, 4, 3} gives 24
But wait, we should exclude the larger negative (value-wise), which is -1
Actually: max negative (value-wise) = max([-2, -1, -1]) = -1
Exclude one -1
Subset: {-2, -1, 4, 3}
Product: (-2) × (-1) × 4 × 3 = 24
Result: 24
Complexity Analysis
- Time Complexity: O(n) - Single pass through array
- Space Complexity: O(1) - Only counting variables
Edge Cases
| Case | Array | Result | |------|-------|--------| | All zeros | [0, 0, 0] | 0 | | Single negative | [-5] | -5 | | One negative, rest zeros | [-1, 0, 0] | 0 | | All negatives (even) | [-2, -3] | 6 | | All negatives (odd) | [-2, -3, -1] | 6 | | Mix with zeros | [-2, 0, 3, 4] | 24 |
Key Takeaways
- Categorize Elements: Separate zeros, negatives, and positives
- Even Negatives: Include all negatives (product is positive)
- Odd Negatives: Exclude the one with smallest absolute value
- Zeros: Never include zeros (they make product 0)
- Special Cases: Handle all zeros, single negative, etc.
- Greedy Choice: Include all positives, pair up negatives
- Edge Case Handling: Critical for correctness