Maximum Strength of a Group - Practice Coding Problems

Maximum Strength of a Group - Problem

Array Dynamic Programming Backtracking Greedy Bit Manipulation Sorting Enumeration Medium

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.

The strength of a group of students at indices i₀, i₁, i₂, ..., iₖ is defined as:

nums[i₀] × nums[i₁] × nums[i₂] × ... × nums[iₖ]

Return the maximum strength of a group the teacher can create.

Input & Output

Example 1 — Mixed Positive and Negative

$ Input: nums = [3,-1,-5,2]

› Output: 30

💡 Note: We can form the group [3,-1,-5,2]. The strength is 3 × (-1) × (-5) × 2 = 30. This is optimal since all elements can be included.

Example 2 — Single Element

$ Input: nums = [-4]

› Output: -4

💡 Note: Since we must form a non-empty group and there's only one element, we must choose [-4] with strength -4.

Example 3 — All Negative with Odd Count

$ Input: nums = [-1,-2,-3]

› Output: 6

💡 Note: The best group is [-2,-3] with strength (-2) × (-3) = 6. Including -1 would make the product negative.

Constraints

1 ≤ nums.length ≤ 13
-9 ≤ nums[i] ≤ 9

Visualization

Tap to expand

Understanding the Visualization

Input

Array of student scores: [3,-1,-5,2]

Process

Find subset with maximum product

Output

Maximum strength: 30

Key Takeaway

🎯 Key Insight: Use all positive numbers and pair negatives to make positives

Asked in

f Meta 3 G Google 2

The key insight is that we want to maximize the absolute value of the product while controlling the sign. The optimal approach uses a greedy strategy: include all positive numbers, pair negative numbers (since two negatives make a positive), and handle edge cases like zeros and single elements. Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Approach	O(n log n)	O(n)	Analyze signs and magnitudes to optimally select elements
Brute Force - Try All Subsets	O(2^n × n)	O(1)	Generate all possible non-empty subsets and find maximum product

Greedy Approach — Algorithm Steps

Separate positive, negative, and zero elements
Sort negatives and positives by absolute value
Greedily select elements to maximize product

Visualization

Tap to expand

Step-by-Step Walkthrough

Separate by Sign

Group positive, negative, and zero elements

Sort by Strategy

Sort to maximize absolute values

Greedy Selection

Use all positives and pair negatives

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int compare_desc(const void* a, const void* b) {
    return (*(int*)b - *(int*)a);
}

int compare_asc(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

long long solution(int* nums, int n) {
    if (n == 1) {
        return nums[0];
    }
    
    int positives[20], negatives[20];
    int pos_count = 0, neg_count = 0;
    int has_zero = 0;
    
    for (int i = 0; i < n; i++) {
        if (nums[i] > 0) {
            positives[pos_count++] = nums[i];
        } else if (nums[i] < 0) {
            negatives[neg_count++] = nums[i];
        } else {
            has_zero = 1;
        }
    }
    
    qsort(positives, pos_count, sizeof(int), compare_desc);
    qsort(negatives, neg_count, sizeof(int), compare_asc);
    
    long long result = 1;
    int used_any = 0;
    
    for (int i = 0; i < pos_count; i++) {
        result *= positives[i];
        used_any = 1;
    }
    
    for (int i = 0; i < neg_count - 1; i += 2) {
        result *= (long long)negatives[i] * negatives[i + 1];
        used_any = 1;
    }
    
    if (!used_any && has_zero) {
        return 0;
    }
    
    if (!used_any) {
        long long max_val = LLONG_MIN;
        for (int i = 0; i < n; i++) {
            if (nums[i] > max_val) {
                max_val = nums[i];
            }
        }
        return max_val;
    }
    
    if (neg_count % 2 == 1) {
        long long last_negative = negatives[neg_count - 1];
        if (result < 0 || (result > 0 && last_negative >= -1)) {
            result *= last_negative;
        }
    }
    
    return result;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting the positive and negative arrays dominates the time complexity

⚡ Linearithmic

Space Complexity

O(n)

Extra arrays to store positive and negative elements

⚡ Linearithmic Space

8.9K Views

Medium Frequency

~15 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler