最大方阵和

1975. 最大方阵和

给你一个 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⁵ <= matrix[i][j] <= 10⁵

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: long long maxMatrixSum(vector<vector<int>>& matrix) { } };

java 解法, 执行用时: 7 ms, 内存消耗: 54.3 MB, 提交时间: 2023-09-28 15:24:08

class Solution {
    public long maxMatrixSum(int[][] matrix) {
        //有0或负数为偶数：abs之和；无0且奇数个负数：abs和减去两倍abs最小的数的abs
        long ans=0;
        int countNega=0;//负数计数
        long minAbs=100001;//记录最小绝对值
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix.length;j++){
                if(matrix[i][j]<0){countNega++;}
                minAbs=Math.min(minAbs,Math.abs(matrix[i][j]));
                ans+=Math.abs(matrix[i][j]);
            }
        }
        if(minAbs>0&&countNega%2==1){ans-=2*minAbs;}
        return ans;
    }
}

golang 解法, 执行用时: 164 ms, 内存消耗: 7.9 MB, 提交时间: 2023-09-28 15:23:40

func maxMatrixSum(matrix [][]int) int64 {
    n := len(matrix)
    cnt := 0 // 负数元素的数量
    var total int64 = 0  // 所有元素的绝对值之和
    var mn  int64 = math.MaxInt64  // 方阵元素的最小绝对值

    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            mn = min(mn, abs(int64(matrix[i][j])))
            if matrix[i][j] < 0 {
                cnt++
            }
            total += abs(int64(matrix[i][j]))
        }

    }

    // 按照负数元素的数量的奇偶性讨论
    if cnt % 2 == 0 {
        return total
    }else {
        return total - 2 * mn
    }
}

func min(a, b int64) int64 { if a < b { return a }; return b }
func abs(a int64) int64 { if a > 0 { return a }; return -a }

python3 解法, 执行用时: 280 ms, 内存消耗: 23.6 MB, 提交时间: 2023-09-28 15:22:31

class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        cnt = 0   # 负数元素的数量
        total = 0   # 所有元素的绝对值之和
        mn = float("INF")   # 方阵元素的最小绝对值
        for i in range(n):
            for j in range(n):
                mn = min(mn, abs(matrix[i][j]))
                if matrix[i][j] < 0:
                    cnt += 1
                total += abs(matrix[i][j])
        # 按照负数元素的数量的奇偶性讨论
        if cnt % 2 == 0:
            return total
        else:
            return total - 2 * mn

cpp 解法, 执行用时: 164 ms, 内存消耗: 34.7 MB, 提交时间: 2023-09-28 15:22:06

class Solution {
public:
    long long maxMatrixSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int cnt = 0;   // 负数元素的数量
        long long total = 0;   // 所有元素的绝对值之和
        int mn = INT_MAX;   // 方阵元素的最小绝对值
        for (int i = 0; i < n; ++i){
            for (int j = 0; j < n; ++j){
                mn = min(mn, abs(matrix[i][j]));
                if (matrix[i][j] < 0){
                    ++cnt;
                }
                total += abs(matrix[i][j]);
            }
        }
        // 按照负数元素的数量的奇偶性讨论
        if (cnt % 2 == 0){
            return total;
        }
        else{
            return total - 2 * mn;
        }
    }
};

上一题

下一题

详情