[Python] Simple line of thought. Faster than 99%
Ok, so let\'s start with the requirements. There\'s a matrix with some positive and negative values. Let\'s forget about the actual values for now, and only con
Ok, so let\'s start with the requirements. There\'s a matrix with some positive and negative values. Let\'s forget about the actual values for now, and only consider the sign. Since we want to obtain the maximum sum of the whole matrix, when we take a pair of adjacent values there can only be three cases: \n- Both are negative: In this case we simply flip both values, and we are done\n- One is positive and one is negative: This is the most interesting! The element that was negative now will be positive, while the element that was positive will now be negative. This is equivalent to moving the negative sign from one cell to another which is adjacent.\n- Both are positive: No need to flip anything.\n\nThinking about the second case led me in 15m to the solution. Let\'s say I\'have found a negative cell X, now I could scan the whole matrix, find another lonely negative cell Y, and using the second case, move the negative from X to a cell adjacent Y and then flip both values using the third case. \n\nAfter this, I realized that there was a catch when the number of negative values was odd, and here the actual values do matter. After doing all the steps, I would still be stuck with a negative cell [since I can move a negative to anywhere in the matrix, but i still need to have two adjacent negatives to make them both positive], but since I could move it around using case 2, I could make sure that the value most close to 0 (ideally 0 itself) would be the only negative.\n\nWhat I did was have the absolute sum of all the values, how many values where negative and the closest value to 0 (minAbsValue). If the number of negative values is odd, I need to remove `minAbsValue` two times, since the first one was a \'miscalculation\' (I considered it to be positive, while in fact was negative) and the second one was simply subtracting the correct value\n\n\n\n```\nclass Solution:\n    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n        negCount = 0\n        absTotal = 0\n        minAbsValue = float(\'inf\')\n        \n        for row in matrix:\n            for val in row:\n                av = abs(val)\n                if av < minAbsValue:\n                    minAbsValue = av\n                \n                absTotal += av\n                if val < 0:\n                    negCount += 1\n        \n        if negCount % 2 == 0:\n            return absTotal\n        else:\n            return absTotal - minAbsValue - minAbsValue\n```
[]