2025-03-26：放三个车的价值之和最大Ⅰ。用go语言，给定一个 m x n 的二维整数数组 board，表示一个国际象棋棋盘，其中每个元素 board[i][j] 代表格子 (i, j) 的价值。在这个棋盘上，我们需要放置三辆车，确保它们之间无法互相攻击，这意味着它们不能位于同一行或同一列。

你需要找出一种放置方式，使得这三辆车所在格子的价值总和最大。请返回这个最大总和。

3 <= m == board.length <= 100。

3 <= n == board[i].length <= 100。

-1000000000 <= board[i][j] <= 1000000000。

输入：board = [[-3,1,1,1],[-3,1,-3,1],[-3,2,1,1]]。

输出：4。

解释：

我们可以将车分别放在格子 (0, 2) ，(1, 3) 和 (2, 1) 处，价值之和为 1 + 1 + 2 = 4 。

题目来自leetcode3256。

大体步骤如下：

1. 初始化三个变量 p[0].x、p[1].x、p[2].x，分别表示最大、次大、第三大的价值，初始值为负无穷。

2. 通过函数 update(row) 来更新当前行的最大、次大、第三大价值的车的位置和价值。在更新的过程中，需要满足车不能在同一列上。

3. 循环遍历整个棋盘的倒数第2行到第1行，更新每一行的最大、次大、第三大价值的车的位置和价值，并保存到 suf 数组中。

4. 对于每个可能的位置放置第二辆车，则在下一行寻找第一辆车和第三辆车的位置。如果这三个位置分别不在同一列，计算它们的价值之和，并更新最大价值。

5. 最后返回计算出的最大价值作为结果。

总的时间复杂度为 O(m * n)，其中 m 代表 board 的行数，n 代表 board 的列数。总的额外空间复杂度为 O(m)。

Go完整代码如下：

package main

import (
	"fmt"
	"math"
)

func maximumValueSum(board [][]int) int64 {
	m := len(board)
	type pair struct{ x, j int }
	suf := make([][3]pair, m)
	p := [3]pair{} // 最大、次大、第三大
	for i := range p {
		p[i].x = math.MinInt
	}
	update := func(row []int) {
		for j, x := range row {
			if x > p[0].x {
				if p[0].j != j { // 如果相等，仅更新最大
					if p[1].j != j { // 如果相等，仅更新最大和次大
						p[2] = p[1]
					}
					p[1] = p[0]
				}
				p[0] = pair{x, j}
			} else if x > p[1].x && j != p[0].j {
				if p[1].j != j { // 如果相等，仅更新次大
					p[2] = p[1]
				}
				p[1] = pair{x, j}
			} else if x > p[2].x && j != p[0].j && j != p[1].j {
				p[2] = pair{x, j}
			}
		}
	}
	for i := m - 1; i > 1; i-- {
		update(board[i])
		suf[i] = p
	}

	ans := math.MinInt
	for i := range p {
		p[i].x = math.MinInt // 重置，计算 pre
	}
	for i, row := range board[:m-2] {
		update(row)
		for j, x := range board[i+1] { // 第二个车
			for _, p := range p { // 第一个车
				for _, q := range suf[i+2] { // 第三个车
					if p.j != j && q.j != j && p.j != q.j { // 没有同列的车
						ans = max(ans, p.x+x+q.x)
						break
					}
				}
			}
		}
	}
	return int64(ans)
}

func main() {
	board := [][]int{{-3, 1, 1, 1}, {-3, 1, -3, 1}, {-3, 2, 1, 1}}
	result := maximumValueSum(board)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def maximum_value_sum(board):
    m = len(board)
    suf = [[(float('-inf'), -1)] * 3 for _ in range(m)]
    p = [(float('-inf'), -1)] * 3  # 最大、次大、第三大

    def update(row):
        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 x > p[1][0] and j != p[0][1]:
                if p[1][1] != j:  # 如果相等，仅更新次大
                    p[2] = p[1]
                p[1] = (x, j)
            elif x > p[2][0] and j != p[0][1] and j != p[1][1]:
                p[2] = (x, j)

    for i in range(m - 1, 1, -1):
        update(board[i])
        suf[i] = p[:]

    ans = float('-inf')
    p = [(float('-inf'), -1)] * 3  # 重置，计算 pre

    for i, row in enumerate(board[:m - 2]):
        update(row)
        for j, x in enumerate(board[i + 1]):  # 第二个车
            for p_value in p:  # 第一个车
                for q_value in suf[i + 2]:  # 第三个车
                    if p_value[1] != j and q_value[1] != j and p_value[1] != q_value[1]:  # 没有同列的车
                        ans = max(ans, p_value[0] + x + q_value[0])
                        break

    return ans

if __name__ == "__main__":
    board = [[-3, 1, 1, 1], [-3, 1, -3, 1], [-3, 2, 1, 1]]
    result = maximum_value_sum(board)
    print(result)