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] <= 105Problem Overview: You are given an n x n integer matrix. You can repeatedly choose two adjacent cells and multiply both values by -1. The goal is to maximize the total sum of the matrix after any number of such operations.
The key observation is that every operation flips the sign of exactly two elements. Because flips happen in pairs, the parity of negative numbers across the matrix becomes the only constraint. Once you recognize this, the problem reduces to maximizing the contribution of absolute values while respecting that parity.
Approach 1: Minimize Overall Negative Signs (Greedy, O(n*m) time, O(1) space)
Treat every element by its absolute value and try to make all numbers positive. Iterate through the matrix once, accumulating the sum of abs(value), counting how many elements are negative, and tracking the smallest absolute value seen. If the number of negatives is even, you can flip signs in pairs until all numbers become positive. If the count is odd, one value must remain negative due to the pair-flip constraint. In that case, subtract 2 * minAbs from the total absolute sum so the smallest magnitude element carries the negative sign. This greedy strategy works because keeping the smallest magnitude negative minimizes the loss in total sum. The algorithm simply scans the matrix once and performs constant-time updates.
Approach 2: Dynamic Adjustment with Parity Check (Greedy reasoning, O(n*m) time, O(1) space)
This method frames the same insight using a running adjustment strategy. While iterating through the grid, maintain three pieces of state: the cumulative absolute sum, the number of negative elements, and the smallest absolute value encountered. After the traversal, evaluate the parity of the negative count. An even count means every element can effectively be turned positive through valid adjacent flips. An odd count forces exactly one negative to remain, so the optimal configuration is the total absolute sum minus twice the smallest absolute value. This formulation highlights the parity constraint explicitly and mirrors how many interview candidates reason through the problem using greedy logic over a grid traversal.
Recommended for interviews: The greedy parity approach is what interviewers expect. It shows you recognized that adjacency operations effectively allow sign propagation across the grid, reducing the problem to counting negatives and tracking the minimum absolute value. A brute-force simulation of sign flips would be unnecessarily complex. Demonstrating the parity insight and finishing with a single pass over the matrix signals strong problem‑solving instincts.
To 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.
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.
Time Complexity: O(n^2); the necessity exists in exploring each point.
Space Complexity: O(1); friendly constant load aside typical iteration encapsulation.
If there is a zero in the matrix, or the number of negative numbers in the matrix is even, then the maximum sum is the sum of the absolute values of all elements in the matrix.
Otherwise, if there are an odd number of negative numbers in the matrix, there will be one negative number left in the end. We choose the number with the smallest absolute value and make it negative, so that the final sum is maximized.
The time complexity is O(m times n), where m and n are the number of rows and columns of the matrix, respectively. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| 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. |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Minimize Overall Negative Signs | O(n*m) | O(1) | Best general solution. Single pass greedy strategy using absolute sum and smallest value tracking. |
| Dynamic Adjustment with Parity Check | O(n*m) | O(1) | Useful when reasoning about parity constraints of negative counts during traversal. |
Maximum Matrix Sum | Simple Thought Process | Leetcode 1975 | codestorywithMIK • codestorywithMIK • 12,138 views views
Watch 9 more video solutions →Practice Maximum Matrix Sum with our built-in code editor and test cases.
Practice on FleetCode