Python | Greedy Pattern
see the Successfully Accepted Submission\n\n# Code\npython3 []\nclass Solution:\n    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n        total_sum 
[see the Successfully Accepted Submission](https://leetcode.com/problems/maximum-matrix-sum/submissions/1461238698/?envType=daily-question&envId=2024-11-24)\n\n# Code\n```python3 []\nclass Solution:\n    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n        total_sum = 0\n        negative_count = 0\n        min_abs_value = float(\'inf\')\n        \n        for row in matrix:\n            for value in row:\n                total_sum += abs(value)\n                if value < 0:\n                    negative_count += 1\n                min_abs_value = min(min_abs_value, abs(value))\n        \n        # If the count of negative numbers is odd, subtract twice the smallest absolute value\n        if negative_count % 2 == 1:\n            total_sum -= 2 * min_abs_value\n        \n        return total_sum\n\n```\n\n# Key Observations\n\n### Effect of Flipping Signs:\n- Multiplying two adjacent elements by \\(-1\\) changes their signs, but their absolute values remain the same.\n\n### Matrix Transformation:\n- The goal is to minimize the number of negative elements. However, if the number of negatives is odd, one negative element will remain. Thus, the **minimum absolute value in the matrix** is critical, as it may need to remain negative.\n\n### Sum Calculation:\n1. Compute the total absolute sum of the matrix.\n2. If there is an odd number of negative values, subtract twice the minimum absolute value to account for the remaining negative element.\n\n---\n\n# Plan\n\n1. Compute the total sum of the absolute values of all elements in the matrix.\n2. Count the number of negative elements.\n3. Find the smallest absolute value in the matrix.\n4. If the number of negative elements is odd, subtract twice the smallest absolute value from the total sum.\n\n---\n\n# Explanation of the Code\n\n### `total_sum`:\n- Keeps track of the sum of absolute values of all elements.\n\n### `negative_count`:\n- Counts the number of negative elements in the matrix.\n\n### `min_abs_value`:\n- Tracks the smallest absolute value, which is critical when handling odd negatives.\n\n### Final Adjustment:\n- If the number of negatives is odd, we adjust the total sum by subtracting twice the smallest absolute value to account for the unchangeable negative.\n\n---\n\n# Complexity\n\n### Time Complexity:\n- \\(O(n^2)\\), as we traverse the entire matrix once.\n\n### Space Complexity:\n- \\(O(1)\\), as we only use scalar variables for computation.\n\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']