最大方阵和

5835. 最大方阵和

难度

给你一个 n x n 的整数方阵 matrix 。你可以执行以下操作 任意次 ：

• 选择 matrix 中 相邻 两个元素，并将它们都 乘以 -1 。

如果两个元素有 公共边 ，那么它们就是 相邻 的。

你的目的是 最大化 方阵元素的和。请你在执行以上操作之后，返回方阵的 最大 和。

示例 1：

输入：matrix = [[1,-1],[-1,1]]
输出：4
解释：我们可以执行以下操作使和等于 4 ：
- 将第一行的 2 个元素乘以 -1 。
- 将第一列的 2 个元素乘以 -1 。

示例 2：

输入：matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]
输出：16
解释：我们可以执行以下操作使和等于 16 ：
- 将第二行的最后 2 个元素乘以 -1 。

提示：

• n == matrix.length == matrix[i].length
• 2 <= n <= 250
• -10^5 <= matrix[i][j] <= 10^5

通过次数1,897

提交次数5,334

贪心算法

如果有偶数个小于0的数字，那么一定可以通过题目所述操作将所有的数字都转换成正数。

如果有奇数个小于0的数字，那么一定可以通过题目所述操作将某个负数转换成最大的负数。

class Solution {
    public long maxMatrixSum(int[][] matrix) {
        long sum1 = 0, sum2 = 0;
        int m = matrix.length;
        int n = matrix[0].length;

        int cnt = 0;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] <= 0) {
                    cnt++;
                    sum1 += matrix[i][j];
                } else {
                    sum2 += matrix[i][j];
                }
                min = Math.min(Math.abs(matrix[i][j]), min);

            }
        }
        if (cnt % 2 == 0) {
            // 如果有偶数个小于0的数字
            return -sum1 + sum2;
        } else {
            // 如果有奇数个小于0的数字
            return -sum1 + sum2 - min * 2;
        }
    }
}

赏

谢谢你请我吃糖果

微信