行列反转所形成的矩阵左上象限的最大和

Question

我正在研究一个 HackerRank 问题，该问题在反转行和列后找到 2N x 2N 矩阵的左上象限中元素的最大总和。例如，如果矩阵是

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

那么将行和列颠倒后可以形成的最大和就是119 + 114 + 56 + 125 = 414得到矩阵后

M' = [
   119  114  42   112
   56   125  101  49
   15   78   56   43
   62   98   83   108
];

反转第 2 列和第 0 行。

我还没有找到一个简单的解决方案，但我提出了一些可能有用的事实：

• 不可能通过反转行和列来获得任何配置。因此，答案不能是简单地对所有元素进行排序并对NxN它们的顶部求和。
• 此外，不可能将任何 1 个元素移动到任何其他位置。例如，(N-1,N-1)处的元素唯一可能被移动的位置是(0,N-1),(N-1,0),(0,0)。
• 从右上象限或左下象限到左上象限需要进行 1 次行反转，从右下象限到左上象限需要进行 2 次反转。
• 不可能提出一个简单地查看左上象限中的每个元素并检查它是否可以被可移动到其位置的元素范围内的更大元素替换的解决方案（例如可以替换M[0,1]=42为M[0,2]=83或M[3,2]=114或M[3,1]=98），因为您还必须考虑在此过程中受到拖累的其他元素。

除了这些事实之外，我想不出任何可以帮助我构建简单解决方案的东西。我是否遗漏了任何明显的事实？昨晚我一直在思考这个问题，直到午夜才睡。:)

Answer 1

(N - 1, N - 1)让我们进一步观察一个元素只能位于(0, 0),(N - 1, 0)或位置这一事实(0, N - 1)。

• 考虑一个(r, c)元素。可以观察到它只能处于以下四种位置之一：(r, c), (N - r - 1, c), (r, N - c - 1)或(N - 1 - r, N - 1 - c)

• 我们可以证明，总是存在一系列操作，将位于上述矩形顶点的四个数字中最大的数字放置到左上象限，而不改变其余部分（为了证明这一点，我们可以只考虑所有案例并提供一个明确的构造来完成它。它很长但很简单，所以我不会在这里发布它）。

• 这两个观察给出了以下解决方案：

  int sum = 0;
  for (int i = 0; i < n / 2; i++)
      for (int j = 0; j < n / 2; j++)
          sum += max(a[i][j], a[i][n - j - 1], a[n - i - 1][j], a[n - i - 1][n - j - 1]); 
  

Answer 2

求方阵中单元格值的最大左上象限总和值。

这里的关键点是，方阵中的每个单元格只能用 3 个其他单元格替换（通过反转行或列 - 通过转置矩阵，反转行，然后再次转置），因此计算（无需改变矩阵）左上象限的最大值，我们只需要计算左上象限中每个单元格可能的最大值。

1. 在（双）“for”循环中：

• 扫描左上象限细胞，
• 对于每个单元格，将其值与其他 3 个可用于替换的值进行比较。
• 使用“//”接收 int（“/”将给出浮点数）

2. 在以下“Sum += ..”代码中：

• 我们可以将当前单元格 [i, j] 值（从左上象限）添加到总和中，
• 或者，为矩阵内可以用 [i, j] 替换的任何单元格添加其他单元格值。
• 方阵中的任何单元格只能用其他 3 个单元格替换，
• 因此，我们选择单元格本身和其他 3 个单元格之间的最大值。

def maxSum(mat):
    R = C = len(mat)
    Sum = 0

    for i in range(0, R // 2):
        for j in range(0, C // 2):
            r1, r2 = i, R - i - 1
            c1, c2 = j, C - j - 1

            Sum += max(mat[r1][c1], mat[r1][c2],
                       mat[r2][c1], mat[r2][c2])

    return Sum


# Testing
if __name__ == "__main__":
    mat = [[112, 42, 83, 119],
           [56, 125, 56, 49],
           [15, 78, 101, 43],
           [62, 98, 114, 108]]

    print(maxSum(mat))  # 414
    exit()