Learning On the Way

1799. Maximize Score After N Operations

You are given nums, an array of positive integers of size 2 * n. You must perform n operations on this array.

In the ith operation (1-indexed), you will:

• Choose two elements, x and y.
• Receive a score of i * gcd(x, y).
• Remove x and y from nums.
• Return the maximum score you can receive after performing n operations.

The function gcd(x, y) is the greatest common divisor of x and y.

def maxScore(self, nums: List[int]) -> int:
    @lru_cache(None)
    def gcd(x, y):
        if x < y:
            x, y = y, x
        
        while True:
            if x % y == 0:
                return y
            x, y = y, x % y
        
    def setbit(x, n): # Cannot directly set because int is immutable
        return x | 1 << n
        
    def getbit(x, n):
        return 1 & (x >> n)
    
    @lru_cache(None)
    def dfs(mask, seq):
        if seq == len(nums) // 2 + 1:
            return 0
        res = 0
        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                if getbit(mask, i) == 0 and getbit(mask, j) == 0:
                    newmask = setbit(setbit(mask, i), j)
                    res = max(res, gcd(nums[i], nums[j]) * seq + dfs(newmask, seq + 1))
        
        return res
        
        return dfs(0, 1)