Easiest Solution!! Beats 100%!! Easiest Approach!!
Intuition\nThe problem asks us to maximize the sum of a matrix by performing operations that involve flipping the sign of adjacent elements. Since we can change
# Intuition\nThe problem asks us to maximize the sum of a matrix by performing operations that involve flipping the sign of adjacent elements. Since we can change the sign of adjacent elements as many times as needed, the key idea is to focus on maximizing the sum by turning as many elements as possible into positive numbers.\n\n- **Maximization Strategy:** We want to ensure that as many elements as possible are positive, because positive numbers contribute to the sum. To achieve this, we should try to flip negative elements to positive by choosing adjacent elements (this is what the operation allows). However, flipping the signs also affects the overall sum, so we need to be strategic.\n\n- **Key Insight:** The sum of the absolute values of all elements is the best we can do if we ignore the sign. However, if there are an odd number of negative elements, we need to make sure the sum is maximized by minimizing the impact of the remaining negative element after flipping.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Sum of Absolute Values:** The first step is to compute the sum of the absolute values of all the matrix elements. This represents the maximum sum we could achieve if all the elements were positive.\n\n1. **Count of Negative Numbers:** Track the number of negative elements in the matrix. If the count of negative numbers is odd, we will have to flip one element back to negative, which reduces the sum slightly.\n\n1. **Minimize the Penalty:** If there are an odd number of negative elements, we will minimize the penalty by subtracting the smallest absolute value from the sum, since flipping the smallest absolute value (the least impactful) will minimize the loss.\n\n1. **Return the Result:** If the number of negative numbers is odd, subtract twice the smallest absolute value from the total sum to account for the fact that one number will have to remain negative.\n\n# Complexity\n- **Time complexity:**  O(n^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- **Space complexity:** O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n![Screenshot 2024-11-24 122151.png](https://assets.leetcode.com/users/images/2c288993-3cb9-46ed-855c-8243f89d1ec0_1732431139.4127398.png)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long maxMatrixSum(vector<vector<int>>& matrix) {\n        long long sum = 0, neg = 0, mini = 1e9;\n\n        for(int i = 0 ; i < matrix.size() ; i++){\n            for(int j = 0 ; j < matrix[0].size() ; j++){\n                if(matrix[i][j] < 0) neg++;\n                if(mini > abs(matrix[i][j]))    mini = abs(matrix[i][j]);\n                sum += abs(matrix[i][j]);\n            }\n        }\n\n        if(neg%2 != 0) sum -= 2*mini;\n        return sum;  \n    }\n};\n```\n![87bab3dd-fabf-4b71-9ac5-984d9015438e_1678160362.0612018.jpeg](https://assets.leetcode.com/users/images/77544edb-ebb6-49a2-9bca-dff6f8045736_1732431164.2045143.jpeg)\n
['Array', 'Greedy', 'Matrix', 'C++']