Python3 | Greedy | Beats 96.45%
Intuition\n\nTwo critical observations form the basis of this solution:\n\n1. Negativity (or the minus sign) can move freely across the matrix.\n2. Two adjacent
# Intuition\n\nTwo critical observations form the basis of this solution:\n\n1. **Negativity (or the minus sign) can move freely across the matrix.**\n2. **Two adjacent negative numbers can neutralize each other to become positive.**\n\nThese observations imply that any pair of negative numbers in the matrix (not necessarily adjacent) can be made positive to maximize the sum. Furthermore, any single negative number can transfer its negativity to the value with the smallest absolute value, further optimizing the total sum.\n\n---\n\n# Approach\n\nBuilding on the intuition, the task is reduced to determining three key elements:\n\n1. The **number of negative values** in the matrix.\n2. The **minimum absolute value** present in the matrix.\n3. The **total sum of absolute values** of all elements.\n\nIf the number of negative values is divisible by 2 (i.e., all negative values can be paired), we can eliminate all negative signs and return the total sum. \n\nIf the number of negative values is not divisible by 2, one negative value will remain unpaired since all others can find their pairs and neutralize. To compute the final answer in this case, we must subtract the minimum absolute value twice from the total sum:\n- Once, because we initially added its absolute value to the total sum.\n- A second time, to account for its actual negative contribution.\n\n---\n\n# Complexity\n\n- **Time Complexity**:  \n  - $$O(1)$$ \u2014 We only use three additional integer variables, so no extra computation beyond iterating over the matrix.\n\n- **Space Complexity**:  \n  - $$O(n \\times m)$$ \u2014 We visit each cell of the matrix exactly once.\n\n---\n\n\n# Code\n```python3 []\nclass Solution:\n    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n        negative_cnt = 0\n        total_sum = 0\n        mini = 10**32\n        for i in range(len(matrix)):\n            for j in range(len(matrix[0])):\n                if matrix[i][j] < 0:\n                    negative_cnt += 1\n                    total_sum += -matrix[i][j]\n                    mini = min(mini, -matrix[i][j])\n                else:\n                    total_sum += matrix[i][j]\n                    mini = min(mini, matrix[i][j])\n        if negative_cnt % 2 == 1:\n            return total_sum - 2*mini\n        else:\n            return total_sum\n```
['Python3']