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.

Examples

Example 1

1
2
3

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

1
2
3

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

Solution

Method 1 – Greedy Product Selection

Intuition

To maximize the product (strength), we want to include as many positive numbers as possible and pair negative numbers to make their product positive. If there is an odd number of negatives, we can exclude the one with the smallest absolute value. If all numbers are negative and only one can be chosen, pick the largest (least negative).

Approach

  1. Separate the numbers into positives, negatives, and count zeros.
  2. Sort negatives by absolute value.
  3. If the number of negatives is odd, exclude the one with the smallest absolute value.
  4. Multiply all positives and the selected negatives.
  5. If the result is empty (no positives or negatives used), return the largest number (could be zero or the least negative).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    long long maxStrength(vector<int>& nums) {
        vector<int> pos, neg;
        for (int x : nums) {
            if (x > 0) pos.push_back(x);
            else if (x < 0) neg.push_back(x);
        }
        sort(neg.begin(), neg.end());
        if (neg.size() % 2) neg.pop_back();
        long long ans = 1;
        bool used = false;
        for (int x : pos) ans *= x, used = true;
        for (int x : neg) ans *= x, used = true;
        if (!used) return *max_element(nums.begin(), nums.end());
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

func maxStrength(nums []int) int64 {
    pos, neg := []int{}, []int{}
    for _, x := range nums {
        if x > 0 {
            pos = append(pos, x)
        } else if x < 0 {
            neg = append(neg, x)
        }
    }
    sort.Ints(neg)
    if len(neg)%2 == 1 {
        neg = neg[:len(neg)-1]
    }
    ans, used := int64(1), false
    for _, x := range pos {
        ans *= int64(x)
        used = true
    }
    for _, x := range neg {
        ans *= int64(x)
        used = true
    }
    if !used {
        mx := nums[0]
        for _, x := range nums {
            if x > mx {
                mx = x
            }
        }
        return int64(mx)
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public long maxStrength(int[] nums) {
        List<Integer> pos = new ArrayList<>(), neg = new ArrayList<>();
        for (int x : nums) {
            if (x > 0) pos.add(x);
            else if (x < 0) neg.add(x);
        }
        Collections.sort(neg);
        if (neg.size() % 2 == 1) neg.remove(neg.size() - 1);
        long ans = 1;
        boolean used = false;
        for (int x : pos) { ans *= x; used = true; }
        for (int x : neg) { ans *= x; used = true; }
        if (!used) {
            int mx = nums[0];
            for (int x : nums) mx = Math.max(mx, x);
            return mx;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun maxStrength(nums: IntArray): Long {
        val pos = mutableListOf<Int>()
        val neg = mutableListOf<Int>()
        for (x in nums) {
            if (x > 0) pos.add(x)
            else if (x < 0) neg.add(x)
        }
        neg.sort()
        if (neg.size % 2 == 1) neg.removeAt(neg.size - 1)
        var ans = 1L
        var used = false
        for (x in pos) { ans *= x; used = true }
        for (x in neg) { ans *= x; used = true }
        if (!used) return nums.maxOrNull()!!.toLong()
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def maxStrength(self, nums: list[int]) -> int:
        pos = [x for x in nums if x > 0]
        neg = sorted([x for x in nums if x < 0])
        if len(neg) % 2:
            neg.pop()
        ans, used = 1, False
        for x in pos:
            ans *= x
            used = True
        for x in neg:
            ans *= x
            used = True
        if not used:
            return max(nums)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn max_strength(nums: Vec<i32>) -> i64 {
        let mut pos = vec![];
        let mut neg = vec![];
        for &x in &nums {
            if x > 0 { pos.push(x); }
            else if x < 0 { neg.push(x); }
        }
        neg.sort();
        if neg.len() % 2 == 1 { neg.pop(); }
        let mut ans: i64 = 1;
        let mut used = false;
        for &x in &pos { ans *= x as i64; used = true; }
        for &x in &neg { ans *= x as i64; used = true; }
        if !used {
            return *nums.iter().max().unwrap() as i64;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    maxStrength(nums: number[]): number {
        const pos = nums.filter(x => x > 0)
        let neg = nums.filter(x => x < 0).sort((a, b) => a - b)
        if (neg.length % 2) neg.pop()
        let ans = 1, used = false
        for (const x of pos) { ans *= x; used = true }
        for (const x of neg) { ans *= x; used = true }
        if (!used) return Math.max(...nums)
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), for sorting the negatives.
  • 🧺 Space complexity: O(n), for storing positives and negatives.