Maximum value sum by placing three rooks ii

Array Dynamic Programming Matrix Enumeration

26.9% acceptance

Feb 25, 2026

You are given a m x n 2D array board. Place three non-attacking rooks to maximize sum of cell values.

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 {
    let m = board.len();
    let n = board[0].len();
    const NEG: i64 = i64::MIN / 2;

    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);
      }
    }
    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);
      }
    }

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

    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;
          }
        }
      }
    }
    ans
  }
}