Find the min of absolute values||beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nGreedy algorithm.\nSince every operation makes the adjacent pair changing signs, it can
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nGreedy algorithm.\nSince every operation makes the adjacent pair changing signs, it can make all values non-negative up to 1 exception, if there are odd number of negative numbers in total.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Tranverse all elements in matrix\n2. Find `minAbs`=the min of absolute values of them\n3. let $sum=\\sum_x |x|$\n4. Count th number of negative numbers\n5. if the number of negative number is odd, then the answer is `sum-2*minAbs` otherwise `sum`\n6. A slight variant is made.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n^2)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long maxMatrixSum(vector<vector<int>>& matrix) {\n        long long sum=0;\n        int minAbs=INT_MAX, cntNeg=0;\n        for(auto& row: matrix){\n            for(int x: row){\n                minAbs=min(minAbs, abs(x));\n                if (x<0){\n                    sum-=x;\n                    cntNeg++;\n                }\n                else{\n                    sum+=x;\n                }\n            }\n        }\n        return (cntNeg&1)?sum-2*minAbs:sum;\n    }\n};\n```\n# A slight variant just considering parity of number of negative numbers thanks to the comment of @Sergei||0ms\n```\nclass Solution {\npublic:\n    long long maxMatrixSum(vector<vector<int>>& matrix) {\n        long long sum=0;\n        int minAbs=INT_MAX;\n        bool negOdd=0;\n        for(auto& row: matrix){\n            for(int x: row){\n                minAbs=min(minAbs, abs(x));\n                if (x<0){\n                    sum-=x;\n                    negOdd=!negOdd;\n                }\n                else sum+=x;\n            }\n        }\n        return sum-2*(negOdd)*minAbs;\n    }\n};\n```
['Array', 'Greedy', 'Matrix', 'C++']