1975. 最大方陣和

思路

假如數組當中一共有偶數個負數，每次操作兩個數字，必定能將所有負數消除。
假如共有奇數個負數，必定會剩下一個負數，並且能任意選擇要讓哪一個數字為負數，
自然就是絕對值最小的那一個。

程式碼

class Solution {
public:
    long long maxMatrixSum(vector<vector<int>>& matrix) {
        int mx_neg = INT_MAX;
        int cnt_neg = 0;
        int m = matrix.size(), n = matrix[0].size();
        long long sum = 0;
        for(auto& mat : matrix) {
            for(auto& x : mat) {
                if(x < 0) {
                    cnt_neg++;
                    x = -x;
                }
                mx_neg = min(mx_neg, x);
                sum += x;
            }
        }
        if(cnt_neg % 2 == 0) return sum;
        return sum - 2 * mx_neg;
    }
};

複雜度分析

• 時間複雜度：$O(mn)$
• 空間複雜度：$O(1)$