如何通过翻转行列生成左上象限和最大的矩阵？

问题背景 #

HackerRank上有一道编程题：允许通过翻转矩阵的任意行或列，找到能让矩阵左上象限元素和最大的方案。我需要实现**返回最终矩阵（而非仅返回最大和）**的功能，目前已有初步实现，但不确定是否为最优方案，希望得到优化建议。

我的算法步骤如下：

• 计算矩阵左上象限的元素和
• 将输入矩阵的数据克隆到变量maxMatrix中
• 翻转某一行
• 检查当前左上象限和是否大于之前的最大和，若是则更新maxMatrix
• 翻转某一列，重复上述检查与更新步骤
• 重复操作直到和达到最大值

当前实现代码 #

public static int upperLeftSum(int[][] arr) {
    int sum = 0;
    
    // 计算左上象限元素和
    for(int l = 0; l < arr.length/2; l++) {
        for(int c = 0; c < arr.length/2; c++) {
            sum += arr[l][c];
        }
    }
    return sum;
}

public static int[][] reverseRow(int[][] arr, int row) {
    // 计算该行左右两半的元素和
    int firsthalf = 0, secondhalf = 0;
    for(int i = 0; i < arr.length/2; i++) {
        firsthalf += arr[row][i];
        secondhalf += arr[row][arr.length - i - 1];
    }
    
    // 如果右半部分和更大，则翻转该行
    if(firsthalf < secondhalf) {
        int start = 0, end = arr.length - 1;
        while(start < end) {
            int temp = arr[row][start];
            arr[row][start] = arr[row][end];
            arr[row][end] = temp;
            start++;
            end--;
        }
    }
    return arr;
}

public static int[][] reverseColumn(int[][] arr, int col) {
    // 计算该列上下两半的元素和
    int firsthalf = 0, secondhalf = 0;
    for(int i = 0; i < arr.length/2; i++) {
        firsthalf += arr[i][col];
        secondhalf += arr[arr.length - i - 1][col];
    }

    // 如果下半部分和更大，则翻转该列
    if(firsthalf < secondhalf) {
        int start = 0, end = arr.length - 1;
        while(start < end) {
            int temp = arr[start][col];
            arr[start][col] = arr[end][col];
            arr[end][col] = temp;
            start++;
            end--;
        }    
    }
    return arr;
}

public static int[][] matrixGame(int[][] arr) {
    int maxSum = upperLeftSum(arr);
    int[][] maxMatrix = new int[arr.length][arr.length];
    
    // 初始化maxMatrix为输入矩阵的克隆
    for(int i = 0; i < arr.length; i++) {
        maxMatrix[i] = arr[i].clone();
    }
    
    int l = 0;
    while(l < arr.length*2) {
        if(l % 2 == 0) {
            arr = reverseRow(arr, l/2);
        } else {
            arr = reverseColumn(arr, l/2);
        }
        
        int sum = upperLeftSum(arr);
        if(sum > maxSum) {
            maxSum = sum;
            // 更新maxMatrix为当前最优矩阵
            for(int i = 0; i < arr.length; i++) {
                maxMatrix[i] = arr[i].clone();
            }
            l = 0; // 重置循环，重新检查所有行和列
        } else {
            l++;
        }
    }
    return maxMatrix;
}

优化建议 #

1. 避免原地修改输入矩阵 #

当前代码中reverseRow和reverseColumn会直接修改输入矩阵，可能导致外部调用时的意外副作用。建议在翻转前先克隆目标行/列，或者克隆整个矩阵再操作，保持输入矩阵的不可变性。

2. 重构迭代逻辑，消除无效循环 #

当前循环通过反复试探行和列的翻转来寻找最优解，最坏情况下时间复杂度较高。实际上，每个行/列的最优状态（是否翻转）是独立的：

• 对任意一行，遍历左上象限的列c，比较arr[row][c]和arr[row][n-1-c]，若后者更大则翻转该行；
• 对任意一列，遍历左上象限的行r，比较arr[r][col]和arr[n-1-r][col]，若后者更大则翻转该列；
  这种方式只需遍历行和列各一次，时间复杂度为O(n²)，效率远高于当前的试探式循环。

3. 减少重复计算，优化求和逻辑 #

当前每次翻转后都重新计算整个左上象限的和，存在大量重复计算。可以在翻转行/列时，仅更新受影响的左上象限元素的和，而非重新遍历整个象限。

4. 补充矩阵规模校验 #

当前代码默认矩阵是偶数阶方阵，需在代码开头添加判断，处理奇数阶矩阵的情况（若题目允许），避免索引越界错误。

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