# Maximum Strength of a Group
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-strength-of-a-group)
Canonical: https://scaleengineer.com/dsa/problems/maximum-strength-of-a-group
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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] <= 9`

# Approaches
## Brute Force using Backtracking
This approach involves generating all possible non-empty subsets of the given `nums` array and calculating the product (strength) for each. The maximum product found among all subsets is the answer. Given the small constraint on the input size (`nums.length <= 13`), exploring all `2^N - 1` non-empty subsets is computationally feasible. We can implement this using a backtracking algorithm.
**Time:** O(2^N), where N is the length of `nums`. For each element, there are two choices (include or exclude), leading to `2^N` total subsets to explore. · **Space:** O(N), where N is the length of `nums`. This space is used by the recursion stack, which can go up to N levels deep.
**Pros:** Conceptually simple and straightforward to implement.; Guaranteed to find the correct answer as it exhaustively checks every possibility.
**Cons:** Highly inefficient for larger input sizes.; The time complexity grows exponentially with the size of the input array.; It is only feasible because of the small problem constraint (nums.length <= 13).
### Explanation
A backtracking function is used to explore all subset combinations. The function, say `backtrack(index, currentProduct, count)`, keeps track of the current index in the array, the product of the elements chosen so far, and the number of elements in the current subset.

For each element, we branch into two recursive calls: one where the element is included in the subset (and its value is multiplied into `currentProduct`), and one where it's excluded. When we reach the end of the array, we have formed a complete subset. If this subset is not empty (which we check using the `count` variable), we compare its product with a globally maintained maximum strength and update it if the current product is greater.

The initial call starts at index 0 with a product of 1 and a count of 0. The use of a `long` for the product is crucial to prevent overflow, as the strength can become very large.

```java
class Solution {
    long maxStrength = Long.MIN_VALUE;

    public long maxStrength(int[] nums) {
        backtrack(0, 1L, 0, nums);
        return maxStrength;
    }

    private void backtrack(int index, long currentProduct, int count, int[] nums) {
        if (index == nums.length) {
            if (count > 0) {
                maxStrength = Math.max(maxStrength, currentProduct);
            }
            return;
        }

        // Choice 1: Include nums[index]
        backtrack(index + 1, currentProduct * nums[index], count + 1, nums);

        // Choice 2: Exclude nums[index]
        backtrack(index + 1, currentProduct, count, nums);
    }
}
```
### Algorithm
- Initialize a global variable `maxStrength` to a very small number (e.g., `Long.MIN_VALUE`).
- Create a recursive function `backtrack(index, currentProduct, count)`. The `count` parameter tracks the number of elements in the current subset to handle the non-empty constraint.
- **Base Case:** If `index` reaches the end of the `nums` array:
  - If `count > 0`, it means the current subset is non-empty. Update the global maximum: `maxStrength = Math.max(maxStrength, currentProduct)`.
  - Return from the function.
- **Recursive Step:** For the element at the current `index`, explore two possibilities:
  1. **Include `nums[index]`**: Make a recursive call `backtrack(index + 1, currentProduct * nums[index], count + 1)`.
  2. **Exclude `nums[index]`**: Make another recursive call `backtrack(index + 1, currentProduct, count)`.
- To start the process, make an initial call `backtrack(0, 1L, 0)` from the main function.
- After the recursion completes, `maxStrength` will hold the maximum product of any non-empty subset.

## Optimal Greedy Approach
A greedy approach provides a highly efficient solution by making locally optimal choices. The key insight is how different types of numbers affect the product. Positive numbers always increase the strength, so we should include all of them. Negative numbers are beneficial in pairs. An even number of negative numbers results in a positive product, while an odd number results in a negative one. If we must have a negative product, we want it to be as close to zero as possible. If we have an odd number of negatives, we can make the product positive by excluding one of them. To maximize the result, we should exclude the negative number with the smallest absolute value (the one closest to zero).
**Time:** O(N), where N is the length of `nums`. The algorithm involves a single pass through the array. · **Space:** O(1). We only use a fixed number of variables to store counts and the running product, regardless of the input size.
**Pros:** Extremely efficient with linear time complexity.; Uses constant extra space, making it optimal for memory usage.; Scales well to much larger input sizes beyond the problem's constraints.
**Cons:** The logic can be complex due to the need to handle multiple edge cases involving zeros, single negative numbers, and combinations thereof.
### Explanation
This approach avoids generating subsets and instead calculates the result based on properties of the numbers in the array. We iterate through the array just once to gather key statistics.

We maintain a running product of all non-zero numbers. We also count the number of positive, negative, and zero elements. Crucially, we keep track of the negative number with the highest value (e.g., -1 is greater than -5).

After the initial pass, we check the count of negative numbers. If it's even, the total product of non-zero numbers is already the maximum possible strength. If the count is odd, the product is negative. To make it positive and maximize it, we must effectively remove one negative number. The best one to remove is the one that has the least impact on the magnitude, which is the negative number with the smallest absolute value (`maxNeg`). We achieve this by dividing our running product by `maxNeg`.

Edge cases are critical: if the array contains only zeros, the answer is 0. If it contains only one negative number and some zeros, the max strength is 0 (by picking a zero instead of the negative number). The code handles these scenarios to ensure correctness.

```java
class Solution {
    public long maxStrength(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }

        long product = 1;
        int negCount = 0;
        int posCount = 0;
        int zeroCount = 0;
        int maxNeg = Integer.MIN_VALUE;
        boolean hasNonZero = false;

        for (int num : nums) {
            if (num > 0) {
                product *= num;
                posCount++;
                hasNonZero = true;
            } else if (num < 0) {
                product *= num;
                negCount++;
                maxNeg = Math.max(maxNeg, num);
                hasNonZero = true;
            } else {
                zeroCount++;
            }
        }

        if (!hasNonZero) { // All zeros
            return 0;
        }

        if (negCount % 2 != 0) { // Odd number of negatives
            // If there's only one negative and no positives, the max strength is 0 (if zeros exist)
            if (negCount == 1 && posCount == 0 && zeroCount > 0) {
                return 0;
            }
            // To maximize, remove the negative number with the smallest absolute value
            product /= maxNeg;
        }

        return product;
    }
}
```
### Algorithm
- Handle the base case: If the array has only one element, its strength is the element itself.
- Initialize variables: `product = 1L`, `negCount = 0`, `posCount = 0`, `zeroCount = 0`, and `maxNeg = Integer.MIN_VALUE` to track the largest negative number (closest to zero).
- Iterate through the `nums` array once to populate these variables.
  - For a positive number, multiply it into `product` and increment `posCount`.
  - For a negative number, multiply it into `product`, increment `negCount`, and update `maxNeg`.
  - For a zero, just increment `zeroCount`.
- After the loop, analyze the counts to determine the final result:
  - If the array contained only zeros, the result is 0.
  - If the count of negative numbers (`negCount`) is odd:
    - A special case: if there are no positive numbers (`posCount == 0`), only one negative number (`negCount == 1`), and at least one zero (`zeroCount > 0`), the maximum strength is 0 (by choosing a zero).
    - Otherwise, to maximize the product, we must remove the effect of one negative number. We remove the one with the smallest absolute value, which is `maxNeg`. This is done by dividing `product` by `maxNeg`.
- If `negCount` is even, the product of all non-zero numbers is already positive and maximized.
- Return the final calculated `product`.

# Solutions
### Java

```java
class Solution {
public
  long maxStrength(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    if (n == 1) {
      return nums[0];
    }
    if (nums[1] == 0 && nums[n - 1] == 0) {
      return 0;
    }
    long ans = 1;
    int i = 0;
    while (i < n) {
      if (nums[i] < 0 && i + 1 < n && nums[i + 1] < 0) {
        ans *= nums[i] * nums[i + 1];
        i += 2;
      } else if (nums[i] <= 0) {
        i += 1;
      } else {
        ans *= nums[i];
        i += 1;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maxStrength(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    if (n == 1) {
      return nums[0];
    }
    if (nums[1] == 0 && nums[n - 1] == 0) {
      return 0;
    }
    long long ans = 1;
    int i = 0;
    while (i < n) {
      if (nums[i] < 0 && i + 1 < n && nums[i + 1] < 0) {
        ans *= nums[i] * nums[i + 1];
        i += 2;
      } else if (nums[i] <= 0) {
        i += 1;
      } else {
        ans *= nums[i];
        i += 1;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxStrength(self, nums: List[int]) -> int: nums . sort() n = len(nums) if n == 1: return nums[0] if nums[1] == nums[- 1] == 0: return 0 ans, i = 1, 0 while i < n: if nums[i] < 0 and i + 1 < n and nums[i + 1] < 0: ans *= nums[i] * nums[i + 1] i += 2 elif nums[i] <= 0: i += 1 else: ans *= nums[i] i += 1 return ans

```