C++ | O(n^2) time, O(1) space | beats 100% | explanation included (hope you like it :D)
Intuition\nIf you found this solution usefull remember to leave an upvote <3 thanks. \n\nThe problem asks us to find the maximum sum of the matrix by mutiplying
# Intuition\nIf you found this solution usefull remember to leave an upvote <3 thanks. \n\nThe problem asks us to find the maximum sum of the matrix by mutiplying 2 adjacent cells by -1. Notice that by moving the index you mutiply at you can move around the (-) sign.\nEx: {-1, 1, 1, 1} -> {1, -1, 1, 1} -> {1, 1, -1, 1}\nTherefore it does not matter where the intial (-) sign is, only how may there are and where you decide to leave the odd (-) after you find all other negative pairs.\n\n# Approach\nWe will make a traversal through the matrix and add all absolute values to a variable sum. At the same time we count how many negative numbers there are and find the number closest to 0 (incase there is a odd (-) sign we can\'t eliminate we take the smallest number to subtract by) call it \'minus\'.\n\nAfter the traversal if there is an odd number of (-)s then we take our sum and subtract \'minus\' twice cause we counted it once already.\n\nIf there is an even number we can be confident that all negatives can be eliminated so we return the sum.\n\n**Keep in mind if there is a 0 in the matrix then we don\'t need to care how many (-)s there are (don\'t worry with the way our code is written it has already taken care of that edge case)\n# Complexity\n- Time complexity: $$O(n^2)$$\n\n- Space complexity:$$O(1)$$\n![image.png](https://assets.leetcode.com/users/images/be118513-38b9-4fab-b527-ee1bcdf24ad7_1732407133.1058471.png)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long maxMatrixSum(vector<vector<int>>& matrix) {\n        long long sum = 0; \n        int minus = INT_MAX, amt = 0;\n        bool zero = false;\n        for(int i = 0; i < matrix.size(); i++){\n            for(int j = 0; j < matrix[0].size(); j++){\n                int tmp = matrix[i][j];\n                sum += abs(tmp);\n                minus = min(minus, abs(tmp));\n                if(tmp < 0) amt++;\n            }\n        }\n        if(amt%2) return sum-minus*2;\n        return sum;\n    }\n};\n```
['C++']