1975. Maximum Matrix Sum

https://leetcode.com/problems/maximum-matrix-sum?envType=daily-question&envId=2026-01-05

這一題我願稱之為腦筋急轉彎之騙到我了。

經過了 542 的洗禮後，我看到每個題目都想了想是否可以用 queue 解。這一題我想到了用 queue 的解法，一開始還瞎開心了很久。接著越寫越怪，很多邊界問題我在想要如何解決，看著 print 出來的內容我思考著，想說怎麼會一大坨一直換位置。突然，靈機一動看到範例二猶如醍醐灌頂。阿不就是只要有偶數個複數他們都可以消掉嗎！只要一直換位置就好了。

==

OK 如果有了這個想法，這題說是 easy 中的 easy 也不為過，以下程式碼廢話不多說：

class Solution {
public:

    vector<int> DIR = {0, 1, 0, -1, 0};

    long long maxMatrixSum(vector<vector<int>>& matrix) {
        long long ans = 0;
        int min_num = std::numeric_limits<int>::max();
        bool neg_count = false;
        int n = matrix.size();
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                
                if (matrix[i][j] < 0) {
                    neg_count = ! neg_count;
                    ans += matrix[i][j]*(-1);
                    min_num = min(min_num, matrix[i][j]*(-1));
                }
                else {
                    ans += matrix[i][j];
                    min_num = min(min_num, matrix[i][j]);
                }
            }
        }
        if (neg_count) {
            ans -= 2 * min_num;
        }

        return ans;
    }
};

Best Solution

因為我的程式碼做法很土炮，附上別人的好看程式碼：

class Solution {
public:
    long long maxMatrixSum(vector<vector<int>>& matrix) {
        long long totalSum = 0;
        int minAbsVal = INT_MAX;
        int negativeCount = 0;

        for (auto& row : matrix) {
            for (int val : row) {
                totalSum += abs(val);
                if (val < 0) {
                    negativeCount++;
                }
                minAbsVal = min(minAbsVal, abs(val));
            }
        }

        // Adjust if the count of negative numbers is odd
        if (negativeCount % 2 != 0) {
            totalSum -= 2 * minAbsVal;
        }

        return totalSum;
    }
};

可以看到他跟我的差別是用 abs 還有 auto 的遍歷，解掉了一些多餘的 index 計算與乘法計算。