You are given an n x n integer matrix. You can do the following operation any number of times:
matrix and multiply each of them by -1.Two elements are considered adjacent if and only if they share a border.
Your goal is to maximize the summation of the matrix's elements. Return the maximum sum of the matrix's elements using the operation mentioned above.
Example 1:
Input: matrix = [[1,-1],[-1,1]] Output: 4 Explanation: We can follow the following steps to reach sum equals 4: - Multiply the 2 elements in the first row by -1. - Multiply the 2 elements in the first column by -1.
Example 2:
Input: matrix = [[1,2,3],[-1,-2,-3],[1,2,3]] Output: 16 Explanation: We can follow the following step to reach sum equals 16: - Multiply the 2 last elements in the second row by -1.
Constraints:
n == matrix.length == matrix[i].length2 <= n <= 250-105 <= matrix[i][j] <= 105To maximize the sum of the matrix, we should aim to minimize the negative influence. Notice that flipping any pair of adjacent elements will keep the number of negative elements consistent in terms of parity (even or odd). Therefore, the key is to ensure the sum of the negative values is minimized while keeping the matrix's parity even, allowing us to theoretically flip elements to achieve a positive parity. It implies that to maximize the sum, the total count of negative numbers should remain even by flipping the sign of the element with the smallest absolute value.
This C solution calculates the absolute sum of the matrix and finds the element with the minimal absolute value. If there's an odd number of negative numbers in the matrix, we subtract twice the minimal absolute to make the total sum maximal, as flipping all negative numbers still requires flipping one more to achieve an even count.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) because we need to iterate over each element in the matrix.
Space Complexity: O(1) as we use a constant amount of additional space.
This approach further explores the combination of summing absolute values and preserving parity. Since the act of flipping adjacent pairs maintains the overall parity of negatives, the challenge is to manage the balance of signs dynamically while ensuring operations help convert the majority of negative numbers or maintain equilibrium by pairing onto the minimal interference possible.
The optimized C version is highly similar to the previous submissions, aiming to calculate the absolute sum through each matrix element while counting negative entries and retrieving the minimum absolute value to handle an odd scenario efficiently for maximal matrix topping-up.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2); the necessity exists in exploring each point.
Space Complexity: O(1); friendly constant load aside typical iteration encapsulation.
| Approach | Complexity |
|---|---|
| Minimize Overall Negative Signs | Time Complexity: O(n^2) because we need to iterate over each element in the matrix. |
| Dynamic Adjustment with Parity Check | Time Complexity: O(n^2); the necessity exists in exploring each point. |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,212 views views
Watch 9 more video solutions →Practice Maximum Matrix Sum with our built-in code editor and test cases.
Practice on FleetCode