Select cells in grid with maximum score

Array Dynamic Programming Bit Manipulation Matrix Bitmask

15.6% acceptance

Feb 25, 2026

226

You are given a 2D matrix grid (up to 10x10, values 1..100). Select cells such that no two are in the same row, and all selected values are distinct. Maximize the sum of selected values.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_score(grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    // For each value 1..=100, record which rows contain it
    let mut row_set = vec![0u32; 101]; // bitmask of rows containing value v
    for (r, row) in grid.iter().enumerate() {
      for &v in row {
        row_set[v as usize] |= 1u32 << r;
      }
    }

    // DP: dp[rows_used] = max score using rows in rows_used mask
    let mut dp = vec![-1i32; 1 << m];
    dp[0] = 0;

    // Process values from highest to lowest for greedy benefit; but DP handles all
    for v in 1..=100usize {
      if row_set[v] == 0 { continue; }
      let rows = row_set[v];
      // Update dp: for each state S and each row r available for v
      let mut new_dp = dp.clone();
      for s in 0..(1u32 << m) {
        if dp[s as usize] < 0 { continue; }
        // Try adding value v from any row r not in s and r is in rows
        let mut avail = rows & !s;
        while avail != 0 {
          let r = avail.trailing_zeros();
          avail &= avail - 1;
          let ns = s | (1u32 << r);
          let cand = dp[s as usize] + v as i32;
          if cand > new_dp[ns as usize] {
            new_dp[ns as usize] = cand;
          }
        }
      }
      dp = new_dp;
    }
    dp.iter().copied().max().unwrap_or(0)
  }
}