[C++] The basic idea is to eliminate negative signs
Recognize that if there is an even amount of negative numbers, you can eliminate all the negatives signs in the following fashion:\n If there is a pair of adjac
Recognize that if there is an even amount of negative numbers, you can eliminate all the negatives signs in the following fashion:\n* If there is a pair of adjacent negative numbers, just remove both negative signs\n* If the remaining negative numbers are separated from each other, just **swap** their negative signs with the adjacent positive number until they are adjacent to each other, and then you can remove 2 negative signs at a time\n\nIf there is an odd amount of negative sign, there will be a negative sign in the end, and we can move that negative sign to the smallest number in the matrix (by *swapping* as above)\n\n**So, if the number of negative signs is even, the answer is the sum of the absolute value of all elements. If it is odd, we will have to minus 2 times the number with smallest absolute value (*for we have to change `+` sign to `-`*) to get the answer:**\n\n```\nclass Solution {\npublic:\n    long long maxMatrixSum(vector<vector<int>>& a) {\n        long long neg_cnt = 0, ans = 0, size = a.size(), minn = 1000000;\n        for (int i = 0; i < size; ++i)\n            for (int j = 0; j < size; ++j) {\n                ans += abs(a[i][j]);\n                if (a[i][j] < 0)\n                    neg_cnt++;\n                minn = minn < abs(a[i][j])? minn: abs(a[i][j]);\n            }\n        if (neg_cnt % 2 == 0)\n            return ans;\n        else \n            return ans - 2*minn;\n    }\n};\n```
[]