Joe Biden can understand this solution (so why not you?!)
Intuition\n Describe your first thoughts on how to solve this problem. \nTake two adjacent elements, one +ve and other -ve. We can see that multiplying them wit
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTake two adjacent elements, one +ve and other -ve. We can see that multiplying them with -1 would change their signs, in other words, the -ve sign \'travels\' from one adjacent element to other.\nThis is the intuition.\n\n![t](https://media1.tenor.com/m/gIFV4QJTwoMAAAAd/walking-with-eagle-joe-biden.gif)\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nCount no. of negative elements (`cn`) and zeros (`c0`) in the matrix. \n\nIf `cn % 2 == 0`, then the -ve signs will travel to be adjacent to each-other and will cancel each other out. Hence, return the sum of absolute values of the elements of the matrix (`ans`).\n\nIf `cn % 2 == 1`, one -ve sign is remaining after the cancelations. If `c0 > 0`, then that -ve sign will travel to be adjacent to a `0`, and multiplying them with -1 would make the element +ve, while 0 remains 0. In this case too, return `ans`.\n\nIn rest cases, one -ve sign will remain after the cancelations, to minimize the sum, we\'ll transfer it to the element having minimum absolute value in the matrix, so that our `ans` variable has to be reduced by the minimum quantity possible. \nAnswer in this case will be `ans - 2 * minn`. (As we had added absolute value of `minn` in `ans` before, we have to remove it twice.)\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n`O(n ^ 2)`\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n`O(1)`\n\nPretty easy question today, don\'t why it\'s labeled medium.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long maxMatrixSum(vector<vector<int>>& matrix) {\n        int n = matrix.size();\n        long long ans = 0;\n        int c0 = 0, cn = 0;\n        int minn = INT_MAX;\n        for (int i = 0; i < n; i++)\n        {\n            for (int j = 0; j < n; j++)\n            {\n                if (matrix[i][j] < 0)\n                    cn++;\n                else if (matrix[i][j] == 0)\n                    c0++;\n                ans += abs(matrix[i][j]);\n                minn = min(minn, abs(matrix[i][j]));\n            }\n        }\n        if ((cn % 2 == 0) || c0 > 0)\n        {\n            return ans;\n        }\n        return ans - 2 * minn;\n    }\n};\n```\nBiden when asked did he really understand the solution?\n![t](https://media1.tenor.com/m/ImO2Gpt5AQgAAAAd/biden-joe-biden.gif)
['Array', 'Greedy', 'Matrix', 'C++']