当前位置：首页 > article >正文

LeetCode 1975. Maximum Matrix Sum

article 2024/11/25 7:38:10

🔗 https://leetcode.com/problems/maximum-matrix-sum

题目

给一个二维数组，里面的元素有正有负
可以对临近的两个元素乘以 -1
求经过若干上述操作，二维数组元素的合的最大值

思路

不能一上来就想模拟，而是要认知到临近的数乘以 -1 带来的变化
对于偶数个负数，经过上述操作，可以都变成正数
对于奇数个负数，经过上述操作，必然有一个数是负数
既然想要二维数组之和最大，在有奇数个负数的时候，让 abs 最小的值为负数即可

踩坑

注意判断位运算的结果，用括号保证优先级，以下两种不同方式，结果是不同的
- (freq & 1) == 0
- freq & 1 == 0

代码

class Solution {
public:
    long long maxMatrixSum(vector<vector<int>>& matrix) {
        long long sum = 0;
        int freq = 0;
        int m = abs(matrix[0][0]);
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                sum += abs(matrix[i][j]);
                if (matrix[i][j] < 0) freq++;
                m = min(m, abs(matrix[i][j])); 
            }
        }
        if ((freq & 1) == 0) return sum;
        else return sum - 2 * m;
    }
};