Easy Approach and Friendly Solution  Beats 100.00% Analyze >
Intuition\n Describe your first thoughts on how to solve this problem. \nTo solve the problem of maximizing the sum of the elements in the given ( n \times n ) 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo solve the problem of maximizing the sum of the elements in the given ( n \\times n ) matrix through the allowed operation of flipping adjacent elements\n# Approach\n<!-- Describe your approach to solving the problem. -->\nwe can follow these steps:\n\nCalculate the Initial Sum: First, compute the sum of all absolute values of the matrix elements. This will give us a baseline for the maximum possible sum if we were able to make all elements positive.\n\nCount Negative Elements: Count how many negative numbers are present in the matrix. This will help us determine how many flips we might need to perform.\n\nCheck the Parity of Negatives: If the count of negative numbers is even, we can convert all of them to positive values through the operations, which means the maximum sum will simply be the sum of the absolute values. If the count is odd, one negative number will remain after all possible flips.\n\nFind the Minimum Absolute Value: If we have an odd count of negative numbers, we need to find the minimum absolute value in the matrix. This is because we will end up with one negative number, and to minimize the loss, we should choose the smallest absolute value to remain negative.\n\nCalculate the Result: If the count of negatives is even, return the total sum of absolute values. If it\'s odd, subtract twice the minimum absolute value from the total sum of absolute values (to account for the one number that remains negative).\n# Complexity\nTime Complexity: ( O(n^2) ), where ( n ) is the dimension of the matrix. We traverse the matrix once.\nSpace Complexity: ( O(1) ) additional space, as we are using only a few variables for calculations.\n\n## Explanation of the Code:\nLoop through the Matrix: We iterate through each element of the matrix to calculate the total sum of absolute values, count the number of negative values, and track the minimum absolute value.\n\nCheck Negatives Count: After processing the matrix, we check if the count of negative numbers is odd.\n\nAdjust the Total Sum: If the count is odd, we subtract twice the minimum absolute value from the total sum to account for the one number that remains negative.\n\nReturn the Result: Finally, we return the computed maximum sum.\n\n\n# Code\n```cpp []\n#include <vector>\n#include <algorithm>\n#include <cmath>\nusing namespace std;\n\nclass Solution {\npublic:\n    long long maxMatrixSum(vector<vector<int>>& matrix) {\n        long long totalSum = 0;\n        int negativeCount = 0;\n        int minAbsValue = INT_MAX;\n\n        // Calculate the total sum of absolute values and count negatives\n        for (const auto& row : matrix) {\n            for (int value : row) {\n                totalSum += abs(value);\n                if (value < 0) {\n                    negativeCount++;\n                }\n                minAbsValue = min(minAbsValue, abs(value));\n            }\n        }\n\n        // If the count of negative numbers is odd, we need to adjust the sum\n        if (negativeCount % 2 != 0) {\n            totalSum -= 2 * minAbsValue; // Subtract twice the smallest absolute value\n        }\n\n        return totalSum;\n    }\n};\n```
['Array', 'Greedy', 'Matrix', 'C++']