Maximum Matrix Sum - Video Solutions

Problem 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.