MediumNo. 2708

Maximum Strength of a Group — LeetCode 2708 Python Solution

Topics
Greedy, Bit Manipulation, Array, Dynamic Programming, Backtracking, Enumeration, Sorting
Reading time
2 min

The 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, ...

Example

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.

Python solution

PythonSolution
class Solution:
    def maxStrength(self, nums: List[int]) -> int:
        ans = -inf
        for i in range(1, 1 << len(nums)):
            t = 1
            for j, x in enumerate(nums):
                if i >> j & 1:
                    t *= x
            ans = max(ans, t)
        return ans

Complexity

Time
O(2n × n)where n is the length of the array
Space · auxiliary
O(1)

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 2708. Maximum Strength of a Group is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0435Non-overlapping IntervalsMedium
0473Matchsticks to SquareMedium
0526Beautiful ArrangementMedium
0638Shopping OffersMedium
0646Maximum Length of Pair ChainMedium
0698Partition to K Equal Sum SubsetsMedium

Frequently asked questions

How hard is LeetCode 2708. Maximum Strength of a Group?

LeetCode 2708. Maximum Strength of a Group is rated Medium on LeetCode.

What is the time complexity of LeetCode 2708. Maximum Strength of a Group?

The Python solution on this page runs in O(2n × n), where n is the length of the array.

What is the space complexity of LeetCode 2708. Maximum Strength of a Group?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 2708. Maximum Strength of a Group cover?

LeetCode 2708. Maximum Strength of a Group is tagged Greedy, Bit Manipulation, Array, Dynamic Programming, Backtracking, Enumeration and Sorting on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.