Maximum Matrix Sum

Maximum Matrix Sum

What is this problem about?

The Maximum Matrix Sum coding problem gives you an n×n matrix of integers. In one operation, you can negate any two adjacent elements (sharing an edge). You can perform any number of operations. Maximize the sum of all elements in the matrix after any sequence of operations. The key insight is that you can "move" a negative sign around the matrix by flipping adjacent pairs.

Why is this asked in interviews?

Honeywell, Microsoft, Amazon, and Google use this problem to test mathematical reasoning under constraints. Candidates who observe that negatives can be "transported" anywhere on the matrix (by flipping adjacent pairs repeatedly) realize the only limitation is parity: you can flip any even number of negatives to positive, but if there's an odd count of negatives, one must remain. This transforms the problem into a simple greedy observation.

Algorithmic pattern used

Greedy observation: Count the number of negative values. If it's even, you can make all values non-negative — sum all absolute values. If it's odd, you must keep one negative, so negate the element with the smallest absolute value and sum all other absolute values. The answer is sum(|all elements|) - 2 * min(|all elements|) when the negative count is odd, or sum(|all elements|) when even.

Example explanation

Matrix: [[1, -1], [-1, 1]]

• Absolute values: [1, 1, 1, 1]. Sum = 4.
• Negatives count = 2 (even). Can make all positive.
• Operation: flip (-1 at [0][1]) and (-1 at [1][0]): now [1, 1; 1, 1]. Sum = 4. Answer = 4.

Matrix: [[1, 2, 3], [-1, -2, -3], [1, 2, 3]]

• Negatives: 3 (odd). Must keep one negative.
• Min absolute value = 1. Answer = (1+2+3+1+2+3+1+2+3) - 2*1 = 18 - 2 = 16.

Common mistakes candidates make

• Simulating the flipping process: Trying to actually perform operations is exponentially complex. The parity observation shortcuts everything.
• Forgetting that zero is the best "negative to keep": If a zero exists and negatives are odd, keep zero negative (it contributes 0 to loss). The minimum absolute value handles this.
• Treating the matrix as 1D: The "adjacent" constraint sounds restrictive but allows moving a sign anywhere on a connected matrix of size ≥ 2, so it's essentially unconstrained on parity.

Interview preparation tip

For the Array Matrix Greedy interview pattern, look for parity-based invariants whenever the problem involves flipping or negating elements. The transformation "what can I achieve?" often boils down to a simple parity condition. State the invariant explicitly in the interview — it demonstrates mathematical insight that impresses interviewers.