Maximum Matrix Sum: Greedy with Negative Count

You are given an n x n integer matrix. In one operation, you can select any two adjacent elements (sharing an edge) and multiply both of them by -1. You can perform this operation any number of times. Return the maximum sum of the matrix's elements.

This is LeetCode 1975: Maximum Matrix Sum, a medium problem that looks like it requires simulation or BFS but collapses into a pure math observation once you see the core insight. No searching, no DP. Just count the negatives and find one value.

Two negatives (even count)

→

↓

All positive, sum = 4

Why this problem matters

Maximum Matrix Sum is a clean example of a problem where the right observation eliminates all complexity. Many candidates start thinking about which cells to flip and in what order. That path leads to exponential search. The winning move is to step back and ask: what states are even reachable?

This style of reasoning, figuring out the invariant before writing any code, shows up in problems involving parity, toggling, and constraint propagation. If you can prove what the final state must look like, the algorithm writes itself.

The key insight

Here is the observation that makes this problem trivial. When you multiply two adjacent elements by -1, you are moving a negative sign from one cell to a neighbor. By chaining these operations, you can effectively teleport a negative sign to any cell in the matrix. Two cells do not need to be adjacent in the original matrix; you just relay the negative through a path of intermediate cells.

This means:

1. If the number of negative values is even, you can eliminate all negatives. Every pair of negatives can cancel each other out through chained flips. The maximum sum is simply the sum of all absolute values.
2. If the number of negative values is odd, exactly one negative must remain. You cannot get rid of the last one because each flip changes the parity of negatives by 0 or 2 (flipping two positives adds 2 negatives, flipping two negatives removes 2, flipping one of each moves it). To maximize the sum, place that remaining negative on the element with the smallest absolute value. That way you lose the least possible.

The formula: sum all absolute values. If the count of negatives is odd, subtract twice the minimum absolute value (because that element contributes its negative value instead of its positive value, a swing of 2 * |value|).

The solution

def maxMatrixSum(matrix):
    total = 0
    min_abs = float("inf")
    neg_count = 0

    for row in matrix:
        for val in row:
            total += abs(val)
            if val < 0:
                neg_count += 1
            if abs(val) < min_abs:
                min_abs = abs(val)

    if neg_count % 2 == 1:
        total -= 2 * min_abs

    return total

The solution scans every cell exactly once. For each cell, it adds the absolute value to a running total, counts negatives, and tracks the minimum absolute value. After the scan, if the negative count is odd, it subtracts 2 * min_abs from the total. That single subtraction accounts for the one negative that cannot be eliminated.

The reason for 2 * min_abs and not just min_abs: the total already includes |min_abs| as a positive contribution. Flipping it to negative means the net effect is -min_abs instead of +min_abs, a difference of 2 * min_abs.

Visual walkthrough

Let's trace through two examples to see how the parity check and minimum absolute value work together. The first example has an even number of negatives (all can be removed). The second has an odd count (one must remain on the smallest element).

In Steps 1 through 3, the even-negative case is clean: just sum all absolute values. Steps 4 through 6 show the odd-negative case, where you must sacrifice the smallest absolute value. The formula sum_abs - 2 * min_abs handles both branches, with the subtraction only applied when neg_count is odd.

Complexity analysis

The matrix has n * n elements, and you scan each one exactly once. No extra data structures are needed; you only maintain three scalar variables. This is optimal since you must read every element at least once.

Edge cases

Before submitting, make sure your solution handles these:

• All positive values: negative count is 0 (even), so the sum is just the sum of all elements. No adjustment needed.
• All negative values in an even-sized set: every negative can pair with another. Sum of absolute values is the answer.
• Single negative in the matrix: odd count. The negative remains on the element with the smallest absolute value. Check whether that element is the negative itself or some other cell with a smaller absolute value.
• A zero in the matrix: minimum absolute value is 0. Even with an odd negative count, 2 * 0 = 0, so the full sum of absolute values is achievable. The zero absorbs the leftover negative sign.
• 1x1 matrix: only one element, no adjacent pairs exist, so no operations are possible. Return the element itself.
• All elements are the same negative value: if n is even, the count of negatives n * n is even (since n * n is even when n is even). If n is odd, n * n is odd, and one negative remains.

The building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Parity counting

The pattern of counting elements that satisfy a condition and using the parity (odd/even) of that count to determine the outcome:

count = 0
for element in collection:
    if condition(element):
        count += 1

if count % 2 == 0:
    result = even_case()
else:
    result = odd_case()

In Maximum Matrix Sum, you count negatives and branch on whether the count is odd or even. In Single Number, you XOR all elements and the parity of duplicates cancels them out. In Bulb Switcher, the parity of divisors determines which bulbs stay on. The skeleton is the same: scan, count, branch on parity.

2. Greedy absolute-value minimization

The pattern of computing the sum of absolute values and then adjusting for a constrained element:

total_abs = sum(abs(x) for x in values)
min_abs = min(abs(x) for x in values)

if must_sacrifice_one:
    total_abs -= 2 * min_abs

This shows up whenever you can freely assign signs to elements but one constraint forces a suboptimal choice. The greedy decision is always to place the penalty on the element where it costs the least. In Maximum Matrix Sum, the constraint is odd parity. In Partition Equal Subset Sum variants, a similar idea of minimizing the gap drives the greedy approach.

Common mistakes

1. Forgetting the factor of 2 in the subtraction. Writing total -= min_abs instead of total -= 2 * min_abs. The total already includes min_abs as positive, so flipping it to negative changes the sum by 2 * min_abs, not just min_abs.

2. Counting zeros as negatives. Zero is not negative. 0 < 0 is false. Make sure your condition is val < 0, not val <= 0. A zero should only affect the min_abs tracking.

3. Trying to simulate the flips. There is no need to actually perform any operations on the matrix. The parity observation means the answer is fully determined by three values: the sum of absolute values, the count of negatives, and the minimum absolute value.

4. Missing the 1x1 edge case. With a 1x1 matrix, there are no adjacent pairs, so no flips are possible. The answer is just matrix[0][0]. The formula still works here because if the single element is negative, neg_count is 1 (odd), and min_abs equals the absolute value of that element, so total - 2 * min_abs gives the original negative value.

From understanding to recall

You have read the greedy observation and it clicks. Count negatives, check parity, subtract 2 * min_abs if odd. Three variables, one loop, one conditional. But can you reproduce this from scratch under interview pressure?

The details that trip people up: using abs(val) consistently, remembering the factor of 2, handling zeros correctly, and not overcomplicating the condition check. These are small details, but they are exactly the kind that cost you points when you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the greedy parity loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "maximize sum with sign flips" and the code flows out without hesitation.

The parity-counting pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Longest Increasing Path in a Matrix - Matrix traversal with strategic element selection
• Gas Station - Greedy decision making with circular structure
• Candy - Greedy algorithm with neighbor-dependent constraints

CodeBricks breaks the maximum matrix sum LeetCode problem into its parity-counting and greedy absolute-value minimization building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy matrix question shows up in your interview, you do not think about it. You just write it.