Maximize Score After N Operations

Maximize Score After N Operations

What is this problem about?

In this problem, you are given an array nums of size 2 * n. You must perform exactly n operations. In the $i$-th operation (1-indexed), you select two elements x and y from the array, remove them, and add i * gcd(x, y) to your score. You need to find the maximum possible total score after performing all n operations.

Why is this asked in interviews?

This is a benchmark problem for Dynamic Programming with Bitmasking. Interviewers ask this to test a candidate's ability to navigate small state spaces ($N \le 7$, array size $\le 14$). It proves you know how to use an integer to represent a boolean array (a bitmask) to cache visited states and avoid explosive backtracking calculations in factorial time complexities.

Algorithmic pattern used

The solution strictly requires DFS Backtracking + Memoization with Bitmasking. The array size is at most 14. An integer bitmask (e.g., 11111111111111 in binary) can represent which numbers are still available. Your recursive function takes (operation_number, current_mask). Inside the function, use two nested loops to iterate through all possible pairs of unpicked numbers (indicated by 0s in the mask). Calculate operation_number * gcd(nums[i], nums[j]), flip their bits to 1 in the mask, and recurse for operation_number + 1. Memoize the max score for each current_mask state.

Example explanation

nums = [1, 2, 3, 4]. Array size is 4, so n = 2 operations. Initial mask = 0000 (binary). Operation = 1.

• Try picking 1 (idx 0) and 2 (idx 1).
  • Score = $1 \times \text{gcd}(1, 2) = 1$.
  • Mask becomes 0011. Recurse to Operation 2.
  • Remaining elements: 3 and 4. Score = $2 \times \text{gcd}(3, 4) = 2$.
  • Total score = $1 + 2 = 3$.
• Try picking 2 (idx 1) and 4 (idx 3).
  • Score = $1 \times \text{gcd}(2, 4) = 2$.
  • Mask becomes 1010. Recurse to Operation 2.
  • Remaining elements 1 and 3. Score = $2 \times \text{gcd}(1, 3) = 2$.
  • Total score = $2 + 2 = 4$. Max score is 4. The DP caches the best score for any given mask.

Common mistakes candidates make

Candidates often try to use Greedy algorithms (e.g., finding the highest GCDs and multiplying them by the highest operation numbers). Greedy utterly fails here because picking a high GCD pair early might consume a number needed for an even better combo later, or vice versa. The state space is small specifically because exhaustive search (DP) is the only mathematically correct approach.

Interview preparation tip

When tackling the Maximize Score After N Operations interview question, look directly at the constraints. When an array size is artificially restricted to $\le 14$ or $\le 20$, it is a blazing siren that you must use Bitmask DP. Practice writing the bitwise checks: (mask & (1 << i)) == 0 (to check if available) and mask | (1 << i) | (1 << j) (to mark as used).