Greedy Algorithm | Beats 100% of user with C++ and Java | Easy Solution
Intuition\nThe problem requires maximizing the sum of the matrix after potentially flipping the signs of elements. A key observation is that flipping the signs 
# Intuition\nThe problem requires maximizing the sum of the matrix after potentially flipping the signs of elements. A key observation is that flipping the signs of elements twice is equivalent to leaving them unchanged, so we can treat the sign flips strategically to optimize the sum.\n\nThe approach leverages:\n\n1. The sum of absolute values of all elements for the initial maximum.\n2. Adjusting for an odd number of negative elements by subtracting twice the smallest absolute value.\n# Approach\n1. Calculate the sum of absolute values: Iterate through the matrix and add up the absolute values of all elements. This provides the baseline maximum sum if all elements were positive.\n2. Count negative numbers: Keep track of how many elements are negative.\n3. Find the minimum absolute value: Identify the smallest absolute value in the matrix to handle adjustments for odd counts of negative numbers.\n4. Adjust for odd negatives: If the count of negative numbers is odd, flipping signs will leave one negative. In that case, subtract twice the smallest absolute value from the sum to get the maximum possible sum.\n# Complexity\n- Time complexity:\nThe algorithm iterates through all \uD835\uDC5B\xD7\uD835\uDC5B elements of the matrix:O(n^2)\n- Space complexity:\nThe solution uses a constant amount of extra space for variables like sum, countNegative, and minValue:O(1)\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long maxMatrixSum(vector<vector<int>>& matrix) {\n      int n = matrix.size();\n      long long sum = 0;\n      int countNegative = 0;\n      int minValue = INT_MAX;\n\n      for(int i=0;i<n;i++){\n        for(int j=0;j<n;j++){\n            sum += abs(matrix[i][j]);\n            if(matrix[i][j] < 0) countNegative++;\n            minValue = min(minValue,abs(matrix[i][j]));\n        }\n      }\n\n      if(countNegative % 2 == 0)  return sum;\n      return sum - 2*minValue;\n    }\n};\n```\n```java []\nclass Solution {\n    public long maxMatrixSum(int[][] matrix) {\n        int n = matrix.length;\n        long sum = 0;\n        int minValue = Integer.MAX_VALUE;\n        int countNegatives = 0;\n\n        for(int i=0;i<n;i++){\n            for(int j=0;j<n;j++){\n                sum += Math.abs(matrix[i][j]);\n                if(matrix[i][j] < 0) countNegatives++;\n                minValue = Math.min(minValue,Math.abs(matrix[i][j]));\n            }\n        }\n\n        if(countNegatives % 2 == 0)  return sum;\n        return sum - 2*minValue;\n    }\n}\n```
['Array', 'Greedy', 'Matrix', 'C++', 'Java']