Maximize score after n operations

Array Math Dynamic Programming Backtracking Bit Manipulation Number Theory Bitmask

57.9% acceptance

Mar 1, 2026

1711

114

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_score(nums: Vec<i32>) -> i32 {
    let m = nums.len();
    let _n = m / 2;
    // precompute gcd for all pairs
    let mut gcd = vec![vec![0i32; m]; m];
    for i in 0..m {
      for j in (i + 1)..m {
        gcd[i][j] = Self::gcd(nums[i], nums[j]);
      }
    }
    // dp[mask] = max score using exactly the elements indicated by mask
    // |mask| must be even; op = popcount/2
    let total = 1 << m;
    let mut dp = vec![0i32; total];
    for mask in 0..total {
      let bits = (mask as u32).count_ones() as usize;
      if bits % 2 != 0 {
        continue;
      }
      let op = bits / 2; // next operation index (1-indexed: op+1)
      // try adding one more pair
      // find first unset bit as first element
      for i in 0..m {
        if mask & (1 << i) != 0 {
          continue;
        }
        for j in (i + 1)..m {
          if mask & (1 << j) != 0 {
            continue;
          }
          let new_mask = mask | (1 << i) | (1 << j);
          let score = (op as i32 + 1) * gcd[i][j];
          if dp[new_mask] < dp[mask] + score {
            dp[new_mask] = dp[mask] + score;
          }
        }
      }
    }
    dp[total - 1]
  }

  fn gcd(a: i32, b: i32) -> i32 {
    if b == 0 { a } else { Self::gcd(b, a % b) }
  }
}