Maximize Score After N Operations — LeetCode 1799 Python Solution
HardBit ManipulationArrayMathDynamic ProgrammingBacktrackingBitmaskNumber Theory
- Problem
- #1799
- Pattern
- Backtracking
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given nums, an array of positive integers of size 2 * n. You must perform n operations on this array.
Example
- Input
- nums = [1,2]
- Output
- 1
- Explanation
- The optimal choice of operations is:
Python solution
Python
class Solution:
def maxScore(self, nums: List[int]) -> int:
m = len(nums)
f = [0] * (1 << m)
g = [[0] * m for _ in range(m)]
for i in range(m):
for j in range(i + 1, m):
g[i][j] = gcd(nums[i], nums[j])
for k in range(1 << m):
if (cnt := k.bit_count()) % 2 == 0:
for i in range(m):
if k >> i & 1:
for j in range(i + 1, m):
if k >> j & 1:
f[k] = max(
f[k],
f[k ^ (1 << i) ^ (1 << j)] + cnt // 2 * g[i][j],
)
return f[-1]Complexity
| Measure | Complexity |
|---|---|
| Time | O(2^m \times m^2) |
| Space | O(2^m) auxiliary |
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 1799. Maximize Score After N Operations 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
Frequently asked questions
- How hard is LeetCode 1799. Maximize Score After N Operations?
- LeetCode 1799. Maximize Score After N Operations is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1799. Maximize Score After N Operations?
- The Python solution on this page runs in O(2^m \times m^2).
- What is the space complexity of LeetCode 1799. Maximize Score After N Operations?
- The Python solution on this page uses O(2^m) auxiliary space.
- What topics does LeetCode 1799. Maximize Score After N Operations cover?
- LeetCode 1799. Maximize Score After N Operations is tagged Bit Manipulation, Array, Math, Dynamic Programming, Backtracking, Bitmask and Number Theory on LeetCode.