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(2^n \times 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.

Maximum Strength of a Group — LeetCode 2708 Python Solution

MediumGreedyBit ManipulationArrayDynamic ProgrammingBacktrackingEnumerationSorting

Problem: #2708
Pattern: Backtracking
Reading time: 2 min
Source: leetcode.com

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

Python

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

Measure	Complexity
Time	O(2^n \times n), where n is the length of the array
Space	O(1) auxiliary

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.

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(2^n \times 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.