> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Maximize Score After N Operations

> Tested Python solution for LeetCode 1799 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 1799, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Math](/catalog/topics/math), [Dynamic Programming](/catalog/topics/dynamic-programming), [Backtracking](/catalog/topics/backtracking), [Bit Manipulation](/catalog/topics/bit-manipulation), [Number Theory](/catalog/topics/number-theory), [Bitmask](/catalog/topics/bitmask). [View on LeetCode](https://leetcode.com/problems/maximize-score-after-n-operations/description/).

Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1799   # by problem number
lcpy gen -s maximize_score_after_n_operations   # by problem name
```

## Problem

\<p>You are given \<code>nums\</code>, an array of positive integers of size \<code>2 \* n\</code>. You must perform \<code>n\</code> operations on this array.\</p>

\<p>In the \<code>i\<sup>th\</sup>\</code> operation \<strong>(1-indexed)\</strong>, you will:\</p>

\<ul>
\<li>Choose two elements, \<code>x\</code> and \<code>y\</code>.\</li>
\<li>Receive a score of \<code>i \* gcd(x, y)\</code>.\</li>
\<li>Remove \<code>x\</code> and \<code>y\</code> from \<code>nums\</code>.\</li>
\</ul>

\<p>Return \<em>the maximum score you can receive after performing \</em>\<code>n\</code>\<em> operations.\</em>\</p>

\<p>The function \<code>gcd(x, y)\</code> is the greatest common divisor of \<code>x\</code> and \<code>y\</code>.\</p>

### Examples

```
Input: nums = [1,2]
Output: 1
Explanation: The optimal choice of operations is:
(1 * gcd(1, 2)) = 1
```

```
Input: nums = [3,4,6,8]
Output: 11
Explanation: The optimal choice of operations is:
(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11
```

```
Input: nums = [1,2,3,4,5,6]
Output: 14
Explanation: The optimal choice of operations is:
(1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14
```

### Constraints

* 1 \<= n \<= 7
* nums.length == 2 \* n
* 1 \<= nums\[i] \<= 10^6

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/maximize_score_after_n_operations/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/maximize_score_after_n_operations/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from math import gcd


class Solution:
    # Time: O(2^m * m^2) where m = len(nums) = 2n <= 14
    # Space: O(2^m)
    def max_score(self, nums: list[int]) -> int:
        m = len(nums)
        gcd_table = [[0] * m for _ in range(m)]
        for i in range(m):
            for j in range(i + 1, m):
                gcd_table[i][j] = gcd_table[j][i] = gcd(nums[i], nums[j])

        full = (1 << m) - 1
        dp = [0] * (1 << m)
        for mask in range(full):
            op = mask.bit_count() // 2 + 1
            for i in range(m):
                if mask >> i & 1:
                    continue
                for j in range(i + 1, m):
                    if mask >> j & 1:
                        continue
                    nxt = mask | 1 << i | 1 << j
                    dp[nxt] = max(dp[nxt], dp[mask] + op * gcd_table[i][j])
        return dp[full]
```

## Complexity

| Time | Space |
| - | - |
| O(2^m \* m^2) where m = len(nums) = 2n \<= 14 | O(2^m) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.