3257. 放三个车的价值之和最大 II
来源第 137 场双周赛 Q4难度困难分数2553
题目描述
给你一个 m x n 的二维整数数组 board ，它表示一个国际象棋棋盘，其中 board[i][j] 表示格子 (i, j) 的 价值 。
处于 同一行 或者 同一列 车会互相 攻击 。你需要在棋盘上放三个车，确保它们两两之间都 无法互相攻击 。
请你返回满足上述条件下，三个车所在格子 值 之和 最大 为多少。
示例 1：
输入：board = [[-3,1,1,1],[-3,1,-3,1],[-3,2,1,1]]
输出：4
解释：
我们可以将车分别放在格子 (0, 2) ，(1, 3) 和 (2, 1) 处，价值之和为 1 + 1 + 2 = 4 。
示例 2：
输入：board = [[1,2,3],[4,5,6],[7,8,9]]
输出：15
解释：
我们可以将车分别放在格子 (0, 0) ，(1, 1) 和 (2, 2) 处，价值之和为 1 + 5 + 9 = 15 。
示例 3：
输入：board = [[1,1,1],[1,1,1],[1,1,1]]
输出：3
解释：
我们可以将车分别放在格子 (0, 2) ，(1, 1) 和 (2, 0) 处，价值之和为 1 + 1 + 1 = 3 。
提示：
3 <= m == board.length <= 5003 <= n == board[i].length <= 500-109 <= board[i][j] <= 109
解法
方法一
思考
与 I 相同，但边长达 \(500\)，即使每行留常数个候选，枚举行三元组仍偏紧，需要按列再筛最大，或对全局最大格点做有限枚举。
核心仍是三枚车行列互异，候选从「每行/每列前几大」中取，避免扫描整盘。题面暂无实现代码，思考依此缩小候选后再验证冲突。
1 | |
1 | |
1 | |
1 | |