DeepSeek LeetCode 3256. 放三个车的价值之和最大 I Rust实现

对于 LeetCode 3256 题“放三个车的价值之和最大 I”，核心逻辑是：三辆车不能在同一行或同一列，且数据规模 (m, n ≤ 100) 下无法直接枚举所有组合。

💡 核心解法

题目要求三个车占据的三个行和三个列互不相同。关键推导出：每一行只需考虑该行价值最大的三个格子（因为其他格子被最优解替代后价值会更高）。因此总枚举次数可控在 \binom{m}{3} \times 3! 量级，十分高效。

💻 Rust 代码实现

```rust

impl Solution {

pub fn maximum_value_sum(board: Vec<Vec<i32>>) -> i64 {

let m = board.len();

let n = board[0].len();

// 存储每一行最大的三个值及列索引

let mut top = vec![vec![(0, 0); 3]; m];

// 预处理每一行最大的三个值

for i in 0..m {

let mut row_vals = (0..n).map(|j| (board[i][j], j)).collect::<Vec<_>>();

row_vals.sort_unstable_by_key(|&(val, _)| -val);

for k in 0..3 {

if k < row_vals.len() {

top[i][k] = row_vals[k];

} else {

top[i][k] = (i32::MIN, 0);

}

}

}

let mut ans = i64::MIN;

// 枚举三行的索引组合 (r1, r2, r3)

for r1 in 0..m {

for k1 in 0..3 {

let (val1, c1) = top[r1][k1];

if val1 == i32::MIN { continue; }

let val1 = val1 as i64;

for r2 in r1+1..m {

for k2 in 0..3 {

let (val2, c2) = top[r2][k2];

if val2 == i32::MIN { continue; }

if c2 == c1 { continue; }

let val2 = val2 as i64;

for r3 in r2+1..m {

for k3 in 0..3 {

let (val3, c3) = top[r3][k3];

if val3 == i32::MIN { continue; }

if c3 == c1 || c3 == c2 { continue; }

let val3 = val3 as i64;

ans = ans.max(val1 + val2 + val3);

}

}

}

}

}

}

ans

}

}

```

🧠 代码步骤详解

1. 预处理核心候选值：遍历 board，对每一行的格子按价值降序排序，保留前三个最大价值及其列索引，存储到 top 数组。

2. 高效三重循环枚举：

· r1 < r2 < r3 保证行号不重复。

· c1, c2, c3 互不相同则列号不重复。

· 计算三个候选值的和 val1 + val2 + val3 并更新全局最大值 ans。

3. 鲁棒性处理：谨慎处理可能不足三列的行，以及最小值 i32::MIN。

该解法通过巧妙的预处理和枚举，在 Rust 中实现了高效且符合题意的解答。