如何修正Python函数以获取2N×2N矩阵左上N×N子矩阵最大和？

问题描述 #

给定一个2N×2N的整数矩阵，可任意次数、任意顺序反转任意行或列，需要计算左上N×N子矩阵（范围从(0,0)到(N–1,N–1)）的最大元素和。

示例 #

原4×4矩阵：

[112, 42, 83, 119,
 56, 125, 56, 49,
 15, 78, 101, 43,
 62, 98, 114, 108]

通过反转第2列和第0行后得到：

[119, 114, 42, 112,
 56, 125, 101, 49,
 15, 78, 56, 43,
 62, 98, 83, 108]

此时左上2×2子矩阵的和为 119+114+56+125=414。

错误代码分析 #

你提供的代码只是执行了固定的反转操作（反转所有行的左右半部分，再反转上下行），这是一种单一的变换方式，无法遍历所有可能的反转组合来找到最优解，因此得到的结果396是错误的。

错误代码：

def seanMatrix(matrix):
    n = len(matrix) // 2
    rows = len(matrix)
    columns = len(matrix[0])

    for i in range(rows):
        for j in range(columns // 2):
            matrix[i][j], matrix[i][columns - j - 1] = matrix[i][columns - j - 1], matrix[i][j]

    for i in range(rows // 2):
        for j in range(columns):
            matrix[i][j], matrix[rows - i - 1][j] = matrix[rows - i - 1][j], matrix[i][j]

    leftSum= 0
    for i in range(n):
        for j in range(n):
            leftSum += matrix[i][j]

    return leftSum

正确解法思路 #

核心观察：对于左上N×N区域内的任意位置(i,j)，通过反转行和列，可以将以下四个对称位置中的任意一个值移动到(i,j)处：

• (i, j)
• (i, 2N-1-j) （同一行的对称列）
• (2N-1-i, j) （同一列的对称行）
• (2N-1-i, 2N-1-j) （对角对称位置）

因此，我们只需要对每组这样的四个位置，选取其中的最大值，累加到总和中，就能得到左上N×N子矩阵的最大可能和。

正确代码实现 #

def max_upper_left_sum(matrix):
    size = len(matrix)
    n = size // 2
    total = 0
    for i in range(n):
        for j in range(n):
            # 获取四个对称位置的值
            val1 = matrix[i][j]
            val2 = matrix[i][size - 1 - j]
            val3 = matrix[size - 1 - i][j]
            val4 = matrix[size - 1 - i][size - 1 - j]
            # 取最大值加到总和
            total += max(val1, val2, val3, val4)
    return total

测试示例 #

用题目中的矩阵测试：

matrix = [
    [112, 42, 83, 119],
    [56, 125, 56, 49],
    [15, 78, 101, 43],
    [62, 98, 114, 108]
]
print(max_upper_left_sum(matrix))  # 输出414，符合预期

内容的提问来源于stack exchange，提问作者micahondiwa