Count negative, O(N), 9ms, 56.43MB
\n\n\n# Intuition \nFor 1 row, if there are even negative numbers, we can flip them all to positive, no matter those negative are adjacent or not. If there are 
![image.png](https://assets.leetcode.com/users/images/260fbac6-8b42-4925-915c-5c631b0ca2aa_1732443966.6039014.png)\n\n\n# Intuition \nFor 1 row, if there are even negative numbers, we can flip them all to positive, no matter those negative are adjacent or not. If there are odd negative numbers, we should sacrifice the minimum absolute value, to let it become negative. For example: \n```\n-5 1 2 -3 -4\n```\nafter several pairly flips, we could leave `1` as negative and make:\n```\n5 -1 2 3 4\n```\n\nNow considering several rows together, it will be the same logic. If it has even negatives in total, we can always flip negatives to neighbours and flip them all to positive. If odd, we should leave the minimum absolute value. \n\nThat comes up with the solution: we add-up all absolute values on-the-go, keep track of the minimum and count negative. At the end, based on the count, we decide it should remove the minimum (twice) or stay the same. \n\n# Approach\nInitialize the result, negative count and minimum absolute value:\n```\n        var result = 0L\n        var negCount = 0\n        var minAbsNum = Int.MAX_VALUE\n```\nIterate the matrix, count negative numbers. Add-up absolute value, update minimum absolute value if needed.\n```\n        for (row in matrix) {\n            for (num in row) {\n                if (num < 0) {\n                    negCount++\n                }\n                val absNum = Math.abs(num)\n                result += absNum\n                minAbsNum = minOf(minAbsNum, absNum)\n            }\n        }\n```\nAfter the iteration, if there are odd negative numbers, we should remove the minimum absolute value **twice**. Removing once is to remove the added-up value during the iteration, and another time is to add its negative value to result.\n```\n        if (negCount % 2 == 1) {\n            result -= minAbsNum * 2\n        }\n        return result\n```\n\n# Complexity\n- Time complexity:\n$$O(n)$$ iteration once\n\n- Space complexity:\n$$O(1)$$\n\n# Code\n```kotlin []\nclass Solution {\n    fun maxMatrixSum(matrix: Array<IntArray>): Long {\n        var result = 0L\n        var negCount = 0\n        var minAbsNum = Int.MAX_VALUE\n        for (row in matrix) {\n            for (num in row) {\n                if (num < 0) {\n                    negCount++\n                }\n                val absNum = Math.abs(num)\n                result += absNum\n                minAbsNum = minOf(minAbsNum, absNum)\n            }\n        }\n        if (negCount % 2 == 1) {\n            result -= minAbsNum * 2\n        }\n        return result\n    }\n}\n```
['Array', 'Greedy', 'Matrix', 'Kotlin']