You are given a 0-indexed integer array nums representing the score of students in an exam. The teacher would like to form one non-empty group of students with maximal strength, where the strength of a group of students of indices i0, i1, i2, ... , ik is defined as nums[i0] * nums[i1] * nums[i2] * ... * nums[ik].
Return the maximum strength of a group the teacher can create.
Example 1:
Input: nums = [3,-1,-5,2,5,-9] Output: 1350 Explanation: One way to form a group of maximal strength is to group the students at indices [0,2,3,4,5]. Their strength is 3 * (-5) * 2 * 5 * (-9) = 1350, which we can show is optimal.
Example 2:
Input: nums = [-4,-5,-4] Output: 20 Explanation: Group the students at indices [0, 1] . Then, we’ll have a resulting strength of 20. We cannot achieve greater strength.
Constraints:
1 <= nums.length <= 13-9 <= nums[i] <= 9Problem Overview: You are given an integer array where each value represents the strength of a member. The task is to select a non-empty subset whose product is maximized. Because the array can contain positive numbers, negative numbers, and zeros, choosing which elements to multiply becomes a careful balancing act.
Approach 1: Backtracking (O(2^n) time, O(n) space)
This method enumerates every possible non-empty subset and computes the product for each. You recursively decide whether to include or exclude each element while maintaining the current product. The maximum product seen during enumeration becomes the result. This approach is conceptually simple and demonstrates the full search space, but it becomes impractical as the array grows because the number of subsets doubles with every new element.
Backtracking is useful when explaining the brute-force baseline during interviews. It also helps illustrate why smarter strategies are needed for larger inputs. The recursion depth is at most n, giving O(n) auxiliary space. However, the exponential O(2^n) runtime makes it unsuitable for production scenarios.
Approach 2: Sorting and Greedy Multiplication (O(n log n) time, O(1) space)
The optimal strategy relies on how multiplication behaves with positive and negative numbers. Positive numbers always increase the product, while negative numbers can increase it only when paired together. Start by sorting the array so negatives and positives are grouped. Multiply all positive numbers. For negatives, pair them from the smallest values (largest magnitude) because the product of two negatives becomes positive.
If there is an odd count of negatives, skip the one closest to zero because including it would flip the sign of the product. Zeros act as neutralizers: if every other choice leads to a negative product, selecting zero can yield a better result. This greedy reasoning ensures you keep only values that contribute positively to the final product.
This approach leverages properties of multiplication rather than exploring every subset. Sorting simplifies pairing logic and ensures the strongest negatives are combined first. The algorithm runs in O(n log n) time due to sorting and uses constant extra space. It commonly appears in problems involving greedy selection and sign management within array processing. Some solutions also connect this reasoning to state transitions similar to dynamic programming maximum-product problems.
Recommended for interviews: Interviewers expect the greedy reasoning. Starting with the backtracking solution shows you understand the brute-force search space, but transitioning to the sorting-based greedy method demonstrates algorithmic insight and the ability to exploit mathematical properties of multiplication.
This approach explores all possible subsets of the given array using backtracking to compute the maximum product (strength). The idea is to explore each index, either including it in the product calculation or not, while keeping track of the current product. If the subset is non-empty, update the maximum strength encountered.
The backtracking function will recursively select or skip each element, updating the product when the element is included, and backtracking to try the next configuration.
This solution uses a recursive backtracking function to explore all subsets of the array. Each call considers the current element either picked or not picked in the subset, updating the product accordingly. The function maintains the maximum product seen across all valid, non-empty subsets.
Time Complexity: O(2^n), where n is the number of elements in the array. This is because we explore every subset.
Space Complexity: O(n), due to the recursive call stack.
This approach involves sorting the array first to easily group the largest elements to maximize the product, taking care of negative numbers' interaction. The strategy involves first taking care of zeroes, then pairing negatives for positive products, and finally selecting the largest positive numbers.
After sorting, we use a greedy technique to pair negatives from the start (most negative) to make products positive, add largest positives, and consider if one last negative or zero as standalone can improve the product depending on the overall product value.
This solution sorts the array and assesses counts of negatives, zeros, and positives. Negatives are paired if possible, and positives are multiplied directly. Handling at the end includes consideration of the largest negative subset pairing.
Time Complexity: O(n log n) due to sorting the array.
Space Complexity: O(1), only a few extra variables are used.
The problem is actually to find the maximum product of all subsets. Since the length of the array does not exceed 13, we can consider using the method of binary enumeration.
We enumerate all subsets in the range of [1, 2^n), and for each subset, we calculate its product, and finally return the maximum value.
The time complexity is O(2^n times n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
First, we can sort the array. Based on the characteristics of the array, we can draw the following conclusions:
nums[1] = nums[n - 1] = 0, then the maximum strength value is 0.0 and the next element is also less than 0, then we multiply these two elements and accumulate the product into the answer. Otherwise, if the current element is less than or equal to 0, we skip it directly. If the current element is greater than 0, we multiply this element into the answer. Finally, we return the answer.The time complexity is O(n times log n), and the space complexity is O(log n). Where n is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Backtracking | Time Complexity: O(2^n), where n is the number of elements in the array. This is because we explore every subset. |
| Approach 2: Sorting and Greedy Multiplication | Time Complexity: O(n log n) due to sorting the array. |
| Binary Enumeration | — |
| Sorting + Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking Enumeration | O(2^n) | O(n) | Understanding the brute-force search space or when n is very small |
| Sorting + Greedy Multiplication | O(n log n) | O(1) | General case; efficiently handles positives, negatives, and zeros |
Maximum Strength of a Group | Leetcode 2708 | BiWeekly 105 • Tech Courses • 728 views views
Watch 7 more video solutions →Practice Maximum Strength of a Group with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor