Maximum Strength of a Group

medium array greedy sorting

Problem

Given an integer array nums of student scores, form one non-empty group whose strength is the product of its members. Return the maximum possible strength. With 1 ≤ nums.length ≤ 13 and −9 ≤ nums[i] ≤ 9, a greedy choice works: multiply every positive number, and use negatives only in pairs so their product stays positive.

Inputnums = [3, -1, -5, 2, 5, -9]

Output1350

Group indices [0,2,3,4,5]: 3 · (−5) · 2 · 5 · (−9) = 1350. We skip −1 because using it would flip the sign and shrink the product.

nums (comma-separated, −9..9)

def maxStrength(nums):
    nums.sort()                       # ascending order
    n = len(nums)
    if n == 1:                        # single student: must take them
        return nums[0]
    prod, count, i = 1, 0, 0
    # pair the most-negative numbers: two negatives make a positive
    while i + 1 < n and nums[i] < 0 and nums[i + 1] < 0:
        prod *= nums[i] * nums[i + 1]
        count += 2
        i += 2
    # multiply in every remaining positive number
    while i < n:
        if nums[i] > 0:
            prod *= nums[i]
            count += 1
        i += 1
    if count == 0:                    # only zeros / one lone negative left
        return max(nums)
    return prod

function maxStrength(nums) {
  nums.sort((a, b) => a - b);          // ascending order
  const n = nums.length;
  if (n === 1) return nums[0];          // single student: must take them
  let prod = 1n, count = 0, i = 0;
  // pair the most-negative numbers: two negatives make a positive
  while (i + 1 < n && nums[i] < 0 && nums[i + 1] < 0) {
    prod *= BigInt(nums[i]) * BigInt(nums[i + 1]);
    count += 2;
    i += 2;
  }
  // multiply in every remaining positive number
  while (i < n) {
    if (nums[i] > 0) { prod *= BigInt(nums[i]); count++; }
    i++;
  }
  if (count === 0) return BigInt(Math.max(...nums)); // zeros / lone negative
  return prod;
}

long maxStrength(int[] nums) {
    Arrays.sort(nums);                  // ascending order
    int n = nums.length;
    if (n == 1) return nums[0];         // single student: must take them
    long prod = 1; int count = 0, i = 0;
    // pair the most-negative numbers: two negatives make a positive
    while (i + 1 < n && nums[i] < 0 && nums[i + 1] < 0) {
        prod *= (long) nums[i] * nums[i + 1];
        count += 2;
        i += 2;
    }
    // multiply in every remaining positive number
    while (i < n) {
        if (nums[i] > 0) { prod *= nums[i]; count++; }
        i++;
    }
    if (count == 0) {                   // zeros / lone negative left
        int best = nums[0];
        for (int v : nums) best = Math.max(best, v);
        return best;
    }
    return prod;
}

long long maxStrength(vector<int>& nums) {
    sort(nums.begin(), nums.end());      // ascending order
    int n = nums.size();
    if (n == 1) return nums[0];          // single student: must take them
    long long prod = 1; int count = 0, i = 0;
    // pair the most-negative numbers: two negatives make a positive
    while (i + 1 < n && nums[i] < 0 && nums[i + 1] < 0) {
        prod *= (long long) nums[i] * nums[i + 1];
        count += 2;
        i += 2;
    }
    // multiply in every remaining positive number
    while (i < n) {
        if (nums[i] > 0) { prod *= nums[i]; count++; }
        i++;
    }
    if (count == 0)                      // zeros / lone negative left
        return *max_element(nums.begin(), nums.end());
    return prod;
}

Explanation

We want the largest product over every non-empty subset. A brute-force scan of all subsets is fine here (length ≤ 13), but a clean greedy after sorting is faster and easy to reason about.

Three facts drive the choice. A positive number always helps the product grow, so we always take it. A negative number flips the sign, so taking one alone hurts — but two negatives multiply to a positive, so negatives are valuable only in pairs. A zero wipes the product to 0, so we never include one unless we have no better option.

After sorting ascending, the most negative numbers sit at the front. We walk a pointer i and greedily grab them two at a time while both nums[i] and nums[i+1] are negative — this multiplies in the largest-magnitude positive contributions first. If there is an odd negative, it is the one closest to zero (smallest magnitude), so dropping it costs the least.

Then we sweep the rest of the array and multiply in every value greater than 0. We keep a count of how many factors we actually used.

The only tricky case is when count stays 0: that means there were no positives and at most one usable negative, so every element is ≤ 0. The best non-empty pick is then simply the single largest element (which is 0 when a zero is present), so we return max(nums). The lone single-element array is handled up front by returning nums[0] directly.

Example: [3,-1,-5,2,5,-9] sorts to [-9,-5,-1,2,3,5]. We pair (−9)·(−5)=45, stop because −1's neighbour 2 is not negative, then multiply 2, 3, 5 to reach 45·30 = 1350.

Time: O(n log n) Space: O(1) (in-place sort)