Maximize Matrix Sum 🚀 | Mathematical Optimization 💡
Intuition \uD83D\uDCA1  \n\nThe problem involves maximizing the sum of elements in an  n \times n  matrix after applying the given operation. The operation allo
# Intuition \uD83D\uDCA1  \n\nThe problem involves maximizing the sum of elements in an $$ n \\times n $$ matrix after applying the given operation. The operation allows adjacent elements to have their signs flipped, which impacts the result based on the parity of negative values in the matrix. Here\'s the plan:  \n\n1. **Absolute Value Contribution**:  \n   Every element\'s absolute value contributes to the total sum regardless of its sign.  \n\n2. **Negative Count and Minimum Absolute Value**:  \n   - If there are an odd number of negative elements, one of them must remain negative in the final configuration.  \n   - To minimize the penalty, we subtract twice the smallest absolute value from the total sum.  \n   - If the number of negatives is even, the entire matrix can be made non-negative, resulting in the sum of all absolute values.  \n\n---\n\n# Approach \uD83D\uDEE0\uFE0F  \n\n1. **Iterate through the Matrix**:  \n   - Calculate the total absolute sum of elements.  \n   - Track the count of negative elements and the smallest absolute value.  \n\n2. **Decision Based on Negatives**:  \n   - If the count of negatives is odd, subtract twice the smallest absolute value.  \n   - Otherwise, return the total absolute sum.  \n\n---\n\n# Complexity \u23F3  \n\n- **Time Complexity**:  \n  $$ O(n^2) $$, where $$ n $$ is the matrix\'s dimension. We iterate over every element once.  \n\n- **Space Complexity**:  \n  $$ O(1) $$, as no additional space is used apart from variables.  \n\n---\n![c1ee5054-dd07-4caa-a7df-e21647cfae9e_1709942227.5165014.png](https://assets.leetcode.com/users/images/25fd7ee6-447a-41ab-9221-516330c93d43_1732415274.964825.png)\n\n\n# Code \uD83D\uDCBB  \n\n```cpp []\n#define ll long long\nclass Solution {\npublic:\n    long long maxMatrixSum(vector<vector<int>>& matrix) {\n        ll absSum = 0;       // Total sum of absolute values\n        int negCount = 0;    // Count of negative numbers\n        int absMin = INT_MAX; // Minimum absolute value in the matrix\n\n        for (const auto& row : matrix) {\n            for (int num : row) {\n                absSum += abs(num);       // Add absolute value to total sum\n                absMin = min(absMin, abs(num)); // Track the smallest absolute value\n                if (num < 0) negCount++;  // Count negatives\n            }\n        }\n\n        // If negative count is odd, subtract twice the smallest absolute value\n        return (negCount % 2 == 1) ? absSum - 2 * absMin : absSum;\n    }\n};\n```\n\n```java []\nclass Solution {\n    public long maxMatrixSum(int[][] matrix) {\n        long absSum = 0;       // Total sum of absolute values\n        int negCount = 0;      // Count of negative numbers\n        int absMin = Integer.MAX_VALUE; // Minimum absolute value in the matrix\n\n        for (int[] row : matrix) {\n            for (int num : row) {\n                absSum += Math.abs(num);          // Add absolute value to total sum\n                absMin = Math.min(absMin, Math.abs(num)); // Track the smallest absolute value\n                if (num < 0) negCount++;          // Count negatives\n            }\n        }\n\n        // If negative count is odd, subtract twice the smallest absolute value\n        return (negCount % 2 == 1) ? absSum - 2L * absMin : absSum;\n    }\n}\n\n```\n\n```python []\nclass Solution:\n    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n        abs_sum = 0          # Total sum of absolute values\n        neg_count = 0        # Count of negative numbers\n        abs_min = float(\'inf\')  # Minimum absolute value in the matrix\n\n        for row in matrix:\n            for num in row:\n                abs_sum += abs(num)          # Add absolute value to total sum\n                abs_min = min(abs_min, abs(num))  # Track the smallest absolute value\n                if num < 0:\n                    neg_count += 1           # Count negatives\n\n        # If negative count is odd, subtract twice the smallest absolute value\n        return abs_sum - 2 * abs_min if neg_count % 2 == 1 else abs_sum\n\n```\n\n```javascript []\n/**\n * @param {number[][]} matrix\n * @return {number}\n */\nvar maxMatrixSum = function(matrix) {\n    let absSum = 0;       // Total sum of absolute values\n    let negCount = 0;     // Count of negative numbers\n    let absMin = Infinity; // Minimum absolute value in the matrix\n\n    for (const row of matrix) {\n        for (const num of row) {\n            absSum += Math.abs(num);          // Add absolute value to total sum\n            absMin = Math.min(absMin, Math.abs(num)); // Track the smallest absolute value\n            if (num < 0) negCount++;          // Count negatives\n        }\n    }\n\n    // If negative count is odd, subtract twice the smallest absolute value\n    return (negCount % 2 === 1) ? absSum - 2 * absMin : absSum;\n};\n\n```\n\n---\n\n# Explanation \uD83D\uDCD8  \n\n### Example 1  \n```plaintext\nInput: \nmatrix = [\n  [1, -1, -2],\n  [-1, 3, 2],\n  [-1, 2, -1]\n]\n\nOutput: 16\n\nExplanation:  \n- Absolute sum:  |1| + |-1| + |-2| + |-1| + |3| + |2| + |-1| + |2| + |-1| = 16  \n- Negatives count} = 5  (odd).  \n- Subtract  2 times 1  (smallest absolute value).  \n- Final result:  16 - 2 = 14.  \n```\n\n### Example 2  \n```plaintext\nInput: \nmatrix = [\n  [1, 2],\n  [3, 4]\n]\n\nOutput: 10\n\nExplanation:  \n- Absolute sum:  1 + 2 + 3 + 4 = 10   \n- Negatives count = 0 (even).  \n- Final result:  10 .  \n```\n\n---\n\n# Takeaway \uD83D\uDE80  \n\nThis solution efficiently balances mathematical insights with code simplicity to handle edge cases like all-positive matrices or extreme negative counts. If you found this helpful, **share and upvote**! \uD83D\uDE0A\n\n![1HBC0324_COV.jpg](https://assets.leetcode.com/users/images/2854d0e2-2103-48d2-8dad-c432eb23bde3_1732415251.2486725.jpeg)\n
['Array', 'Greedy', 'Matrix', 'C++', 'Java', 'Python3', 'JavaScript']