Java Solution for Maximum Matrix Sum Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe goal is to maximize the sum of the matrix elements by flipping the signs of adjacen
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe goal is to maximize the sum of the matrix elements by flipping the signs of adjacent elements. The key insights are:\n1.\tSign Manipulation:\n\t\u2022\tFlipping adjacent elements\u2019 signs means that all elements\u2019 signs can potentially be controlled, except in cases where there\u2019s an odd number of negative numbers. This is because flipping signs an odd number of times leaves at least one negative value.\n2.\tAbsolute Sum Maximization:\n\t\u2022\tTo maximize the sum, the absolute values of all elements should be added, and we minimize the penalty caused by unavoidable negative elements (if the negative count is odd).\n3.\tHandling Odd Negatives:\n\t\u2022\tIf the count of negative numbers is odd, we must leave one element negative, so the smallest absolute value is subtracted twice to minimize the loss\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tTraverse the Matrix:\n\t\u2022\tCalculate the total sum of the absolute values of all elements (totalSum).\n\t\u2022\tCount the number of negative elements (negativeCount).\n\t\u2022\tTrack the smallest absolute value in the matrix (minAbsValue).\n2.\tAdjust for Odd Negatives:\n\t\u2022\tIf negativeCount is even, all negatives can be flipped to positive, and the result is the totalSum.\n\t\u2022\tIf negativeCount is odd, we subtract twice the smallest absolute value (2 * minAbsValue) to account for the unavoidable negative element.\n3.\tReturn the Result:\n\t\u2022\tDepending on the parity of negativeCount, return the adjusted or unadjusted totalSum.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nMatrix Traversal: The solution iterates through every element in the n x n matrix exactly once.\n\u2022\tTime Complexity: O(n^2)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nExtra Variables: Only a few variables (totalSum, negativeCount, and minAbsValue) are used to store intermediate results.\n\u2022\tSpace Complexity: O(1)\n\n# Code\n```java []\nclass Solution {\n    public long maxMatrixSum(int[][] matrix) {\n        long totalSum = 0;\n        int minAbsValue = Integer.MAX_VALUE;\n        int negativeCount = 0;\n\n        for (int i = 0; i < matrix.length; i++) {\n            for (int j = 0; j < matrix[i].length; j++) {\n                int value = matrix[i][j];\n                totalSum += Math.abs(value); \n                minAbsValue = Math.min(minAbsValue, Math.abs(value)); \n                if (value < 0) {\n                    negativeCount++; \n                }\n            }\n        }\n\n        if (negativeCount % 2 != 0) {\n            totalSum -= 2 * minAbsValue;\n        }\n\n        return totalSum;\n    }\n}\n```
['Java']