🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏
\n\n---\n\n\n## Intuition\nThe problem asks us to maximize the sum of a matrix\'s elements while potentially flipping the signs of some elements. Observations:\
![image.png](https://assets.leetcode.com/users/images/ec076301-c25c-4bbb-8a53-020b4b2a93f9_1732898312.1336663.png)\n\n---\n\n\n## Intuition\nThe problem asks us to maximize the sum of a matrix\'s elements while potentially flipping the signs of some elements. Observations:\n1. The absolute values of the numbers determine the sum; flipping a negative number to positive increases the sum.\n2. The result depends on whether the count of negative numbers is even or odd:\n   - **Even negatives**: All can be flipped to positive, resulting in the maximum sum.\n   - **Odd negatives**: At least one negative must remain. To minimize its impact, we subtract twice the smallest absolute value from the total absolute sum.\n\n---\n\n## Approach\n1. **Calculate the total absolute sum** of all matrix elements.\n2. **Count the negative numbers** in the matrix.\n3. **Track the smallest absolute value** for cases where the number of negatives is odd.\n4. **Determine the final result**:\n   - If the count of negatives is even, return the total absolute sum.\n   - If odd, subtract \\( 2 \\times \\text{(smallest absolute value)} \\) from the absolute sum to account for the single negative.\n\n---\n\n## Complexity\n- **Time Complexity**:  \n  \\(O(n^2)\\), where \\(n\\) is the dimension of the square matrix.  \n  We iterate through each element once.\n\n- **Space Complexity**:  \n  \\(O(1)\\), as no extra space is used apart from a few variables.\n\n---\n\n\n```dart []\nimport \'dart:math\';\n\nclass Solution {\n  int maxMatrixSum(List<List<int>> matrix) {\n    int n = matrix.length;\n    int negativeCount = 0;\n    int absSum = 0;\n    int smallestAbsValue = 100000; // A very large number within constraints\n\n    for (int i = 0; i < n; i++) {\n      for (int j = 0; j < n; j++) {\n        int value = matrix[i][j];\n        absSum += value.abs();\n        if (value < 0) negativeCount++;\n        smallestAbsValue = min(smallestAbsValue, value.abs());\n      }\n    }\n\n    // If the number of negatives is even, return the absolute sum\n    if (negativeCount % 2 == 0) return absSum;\n\n    // If odd, subtract twice the smallest absolute value\n    return absSum - 2 * smallestAbsValue;\n  }\n}\n```\n\n\n```java []\nimport java.util.*;\n\npublic class Solution {\n    public long maxMatrixSum(int[][] matrix) {\n        int n = matrix.length;\n        int negativeCount = 0;\n        long absSum = 0;\n        int smallestAbsValue = Integer.MAX_VALUE;\n\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                int value = matrix[i][j];\n                absSum += Math.abs(value);\n                if (value < 0) negativeCount++;\n                smallestAbsValue = Math.min(smallestAbsValue, Math.abs(value));\n            }\n        }\n\n        if (negativeCount % 2 == 0) return absSum;\n\n        return absSum - 2L * smallestAbsValue;\n    }\n}\n```\n\n\n```python []\nclass Solution:\n    def maxMatrixSum(self, matrix: List[List[int]]) -> int:\n        n = len(matrix)\n        negative_count = 0\n        abs_sum = 0\n        smallest_abs_value = float(\'inf\')\n\n        for i in range(n):\n            for j in range(n):\n                value = matrix[i][j]\n                abs_sum += abs(value)\n                if value < 0:\n                    negative_count += 1\n                smallest_abs_value = min(smallest_abs_value, abs(value))\n\n        if negative_count % 2 == 0:\n            return abs_sum\n\n        return abs_sum - 2 * smallest_abs_value\n```\n\n\n```javascript []\nvar maxMatrixSum = function(matrix) {\n    const n = matrix.length;\n    let negativeCount = 0;\n    let absSum = 0;\n    let smallestAbsValue = Infinity;\n\n    for (let i = 0; i < n; i++) {\n        for (let j = 0; j < n; j++) {\n            let value = matrix[i][j];\n            absSum += Math.abs(value);\n            if (value < 0) negativeCount++;\n            smallestAbsValue = Math.min(smallestAbsValue, Math.abs(value));\n        }\n    }\n\n    if (negativeCount % 2 === 0) return absSum;\n\n    return absSum - 2 * smallestAbsValue;\n};\n```\n\n\n```cpp []\n#include <vector>\n#include <cmath>\n#include <algorithm>\nusing namespace std;\n\nclass Solution {\npublic:\n    long long maxMatrixSum(vector<vector<int>>& matrix) {\n        int n = matrix.size();\n        int negativeCount = 0;\n        long long absSum = 0;\n        int smallestAbsValue = INT_MAX;\n\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                int value = matrix[i][j];\n                absSum += abs(value);\n                if (value < 0) negativeCount++;\n                smallestAbsValue = min(smallestAbsValue, abs(value));\n            }\n        }\n\n        if (negativeCount % 2 == 0) return absSum;\n\n        return absSum - 2LL * smallestAbsValue;\n    }\n};\n```\n\n\n```go []\npackage main\n\nimport "math"\n\nfunc maxMatrixSum(matrix [][]int) int64 {\n    n := len(matrix)\n    negativeCount := 0\n    absSum := int64(0)\n    smallestAbsValue := math.MaxInt32\n\n    for i := 0; i < n; i++ {\n        for j := 0; j < n; j++ {\n            value := matrix[i][j]\n            absSum += int64(abs(value))\n            if value < 0 {\n                negativeCount++\n            }\n            if abs(value) < smallestAbsValue {\n                smallestAbsValue = abs(value)\n            }\n        }\n    }\n\n    if negativeCount%2 == 0 {\n        return absSum\n    }\n    return absSum - 2*int64(smallestAbsValue)\n}\n\nfunc abs(x int) int {\n    if x < 0 {\n        return -x\n    }\n    return x\n}\n```\n\n---\n\n![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style=\'width:250px\'}\n
['Array', 'Greedy', 'C', 'Matrix', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'Dart']