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

我正在研究一个 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 行。

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

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

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

让我们进一步观察一个元素(N - 1, N - 1)只能在(0, 0), (N - 1, 0) or (0, N - 1)位置。

• 考虑一个(r, c)元素。可以观察到它只能处于以下四种位置之一：(r, c), (N - r - 1, c), (r, N - c - 1) or (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]);