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

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 个其他单元格（通过反转行或列 - 通过转置矩阵，反转行，然后再次转置）， 因此计算（不改变矩阵）左上象限的最大值， 我们只需要计算左上象限中每个单元格可能的最大值。

在（双）“for”循环中：

扫描左上象限细胞，

• 对于每个单元格，将其值与其他 3 个可用于替换的值进行比较。
• 使用'//'接收一个int（'/'将给出一个float）

在以下“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()

Answer 3

(2 * N)

，其中 N 分别是行数和列数。 （N行可以反转，N列可以反转。）

这里，对于问题中的4x4矩阵，有相应的解决方案：

let data = 
    let values = 
        [|
            112;  42 ;  83;   119;
            56 ;  125;  56;   49;
            15 ;  78 ;  101;  43;
            62 ;  98 ;  114;  108
        |]
    Array2D.init 4 4 (fun r c -> values.[4 * r + c])

let upperQuadrantSum (m : int[,]) = 
    [ for r in 0..1 do for c in 0..1 do yield (r,c) ]
    |> List.sumBy (fun (r,c) -> m.[r,c])

let reverseRow row (m : int[,])  =
    Array2D.init 4 4 (fun r c -> if r = row then m.[r,3-c] else m.[r,c])
let reverseCol col (m : int[,]) =
    Array2D.init 4 4 (fun r c -> if c = col then m.[3-r,c] else m.[r,c])

let possibleActions = 
    [   reverseRow 0; reverseRow 1; reverseRow 2; reverseRow 3; 
        reverseCol 0; reverseCol 1; reverseCol 2; reverseCol 3; 
    ]

let maximize metric maxDepth m0 =
    let rec search depth m =
        let value = metric m
        if depth = maxDepth 
        then value
        else
            possibleActions 
            |> List.map (fun a -> let m1 = a m in max (metric m1) (search (depth+1) m1))
            |> List.max
            |> fun msearch -> max value msearch
    search 0 m0

let solve = maximize upperQuadrantSum

在 fsi 中，发行： 

解决7个数据;;

验证它：int = 414

当然，正如另一个答案中所述，一旦想到优化， 很高兴有蛮力解决方案来验证两者都产生 相同的结果：

let inline solve1 m = 
    let n = Array2D.length1 m
    let candidates r c =
        [ r,c ; n-1-r,c ; r,n-1-c ; n-1-r,n-1-c ]
    [
        for r in 0..n/2-1 do
            for c in 0..n/2-1 do
                yield (candidates r c |> List.map (fun (r,c) -> m.[r,c]) |> List.max)
    ] |> List.sum

solve1 data

抱歉没有用 C# 编写代码，但是 .fsx 文件和 fsi 比创建另一个 C# 应用程序要容易得多...

Answer 4

#Turn it into numpy for maximum pleasure
matrix=np.array(matrix)

#Measure its leangth
l=len(matrix)
ml=int(l/2)

#Move throught the four "corners" or "the-only-four-places-where-you-can-find-the-maximum-of-each-quadrant's-element"
max_vals = \
    [
        max(
            matrix[i,j],
            matrix[i,-(j+1)], 
            matrix[-(i+1),j],
            matrix[-(i+1),-(j+1)]
        )
        for j in range(ml)
        for i in range(ml)
    ]

#Return the sum of values
sum(max_vals)

Answer 5

112     42      83      119

56      125     56      49

15      78      101     43

62      98      114     108

定义为：

A1      B1      B2      A2

C1      D1      D2      C2

C3      D3      D4      C4

A3      B3      B4      A4

现在我们必须找到其中最大的总和值，

A1 + A2 + A3 + A4,
C1 + C2 + C3 + C4,
D1 + D2 + D3 + D4

可以通过以下方式实现：

public static void MockTest(List<List<int>> matrix)
{
    int length = matrix.Count;
    int halfLength = length / 2;
    length--;
    int sum = 0;

    for (int i = 0; i < halfLength; i++)
    {
        for (int j = 0; j < halfLength; j++)
        {
            int a1 = matrix[i][j];
            int a2 = matrix[i][length - j];
            int a3 = matrix[length - i][j];
            int a4 = matrix[length - i][length - j];

            int[] elements = { a1, a2, a3, a4 };
            sum += elements.Max();
        }
    }

    Console.WriteLine(sum);   
   
}