Maximize Score After N Operations LeetCode solution in Python

1
# Runtime: 6454 ms (Top 9.35%) | Memory: 24.7 MB (Top 37.40%)
2
from functools import lru_cache
3

4

5
class Solution:
6
    def maxScore(self, nums: List[int]) -> int:
7
        def gcd(a, b):
8
            while a:
9
                a, b = b % a, a
10
            return b
11

12
        halfplus = len(nums) // 2 + 1
13

14
        @lru_cache(None)
15
        def dfs(mask, k):
16
            if k == halfplus:
17
                return 0
18
            res = 0
19
            for i in range(len(nums)):
20
                for j in range(i + 1, len(nums)):
21
                    if not (mask & (1 << i)) and not (mask & (1 << j)):
22
                        res = max(
23
                            res,
24
                            k * gcd(nums[i], nums[j])
25
                            + dfs(mask | (1 << i) | (1 << j), k + 1),
26
                        )
27
            return res
28

29
        return dfs(0, 1)