title
给你一个 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
solution
枚举中间的，前后缀结合，每行取最大的3个值。
class Solution:
def maximumValueSum(self, board: List[List[int]]) -> int:
def update(row: List[int]) -> None:
for j, x in enumerate(row):
if x > p[0][0]:
if p[0][1] != j: # 如果相等，仅更新最大
if p[1][1] != j: # 如果相等，仅更新最大和次大
p[2] = p[1]
p[1] = p[0]
p[0] = (x, j)
elif j != p[0][1] and x > p[1][0]:
if p[1][1] != j: # 如果相等，仅更新次大
p[2] = p[1]
p[1] = (x, j)
elif j != p[0][1] and j != p[1][1] and x > p[2][0]:
p[2] = (x, j)
m = len(board)
suf = [None] * m
p = [(-inf, -1)] * 3 # 最大、次大、第三大
for i in range(m - 1, 1, -1):
update(board[i])
suf[i] = p[:]
ans = -inf
p = [(-inf, -1)] * 3 # 重置，计算 pre
for i, row in enumerate(board[:-2]):
update(row)
for j2, y in enumerate(board[i + 1]): # 第二个车
for x, j1 in p: # 第一个车
for z, j3 in suf[i + 2]: # 第三个车
if j1 != j2 and j1 != j3 and j2 != j3: # 没有同列的车
ans = max(ans, x + y + z) # 注：手动 if 更快
break
return ans