Maximum value sum by placing three rooks i

Array Dynamic Programming Matrix Enumeration

16.4% acceptance

Feb 25, 2026

109

You are given a m x n 2D array board. Place three rooks (non-attacking) to maximize the sum of cell values. Rooks in the same row or column attack each other.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_value_sum(board: Vec<Vec<i32>>) -> i64 {
    Self::solve(&board)
  }

  pub fn solve(board: &Vec<Vec<i32>>) -> i64 {
    let m = board.len();
    let n = board[0].len();
    const NEG: i64 = i64::MIN / 2;

    // Compute prefix and suffix column maximums
    // prefix_col[r][c] = max board[r'][c] for r' < r (NEG if none)
    let mut pcol = vec![vec![NEG; n]; m];
    for r in 1..m {
      for c in 0..n {
        pcol[r][c] = pcol[r - 1][c].max(board[r - 1][c] as i64);
      }
    }
    // scol[r][c] = max board[r'][c] for r' > r
    let mut scol = vec![vec![NEG; n]; m];
    for r in (0..m - 1).rev() {
      for c in 0..n {
        scol[r][c] = scol[r + 1][c].max(board[r + 1][c] as i64);
      }
    }

    // top3(vals): top-3 (val, col) sorted descending
    let top3 = |vals: &[i64]| -> Vec<(i64, usize)> {
      let mut v: Vec<(i64, usize)> = vals
        .iter()
        .enumerate()
        .map(|(c, &val)| (val, c))
        .collect();
      v.sort_unstable_by(|a, b| b.0.cmp(&a.0));
      v.truncate(3);
      v
    };

    // row top3 for each row
    let row3: Vec<Vec<(i64, usize)>> = (0..m)
      .map(|r| {
        top3(&board[r].iter().map(|&x| x as i64).collect::<Vec<_>>())
      })
      .collect();

    let mut ans = NEG;
    for r2 in 0..m {
      let pref3 = top3(&pcol[r2]);
      let suf3 = top3(&scol[r2]);
      for &(v2, c2) in &row3[r2] {
        for &(v1, c1) in &pref3 {
          if c1 == c2 || v1 == NEG { continue; }
          for &(v3, c3) in &suf3 {
            if c3 == c2 || c3 == c1 || v3 == NEG { continue; }
            ans = ans.max(v2 + v1 + v3);
            break; // first valid c3 is the best for this c1
          }
        }
      }
    }
    ans
  }
}