LeetCode 1975: Maximum Matrix Sum Explained | Optimal Solution & Code

Problem (rephrased)

You’re given an n x n integer matrix. You may perform the following operation any number of times:

• Pick two adjacent cells (share an edge) and multiply both values by -1.

Your goal is to maximize the sum of all elements in the matrix.

Key Insight

The operation flips the signs of exactly two adjacent cells.

So, ignoring zeros for a moment:

• Flipping two numbers changes the count of negative numbers by an even amount (0, 2, or -2).
• Therefore, the parity (odd/even) of the number of negative elements is an invariant: it does not change.

Why adjacency doesn’t really restrict us

Even though you can only flip adjacent pairs, the grid is connected. Using a path of adjacent flips, you can effectively “transport” a sign flip across the matrix.

A common way to see it:

• Consider any path between two cells A and B.
• If you apply the operation along each edge on the path (in order), every internal cell gets flipped twice (cancels out), while only endpoints get flipped once.
• Net effect: you can flip the signs of any two cells you want, while leaving all others unchanged.

✅ Result: The only real global restriction is parity of negatives (unless there’s a zero, discussed next).

---

What’s the best possible sum?

Step 1: “Ideal world” — make everything positive

If you could choose signs freely, you’d turn every element into |a[i][j]|, giving: absSum=∑∣aij∣\text{absSum} = \sum |a_{ij}|absSum=∑∣aij​∣

That’s the maximum possible sum of magnitudes.

Step 2: Parity constraint decides if you can reach that ideal

Case A: Number of negatives is even

You can pair up negatives and flip them away (conceptually), so you can make all values non-negative.

✅ Answer = absSum

Case B: Number of negatives is odd

If there is no zero, parity cannot change, meaning:

• You cannot make all numbers positive.
• You must leave exactly one number negative.

To maximize the final sum, the negative one should hurt as little as possible → choose the element with the smallest absolute value.

If minAbs = min |a[i][j]|, then leaving -minAbs instead of +minAbs reduces the total by 2 * minAbs: answer=absSum−2⋅minAbs\text{answer} = \text{absSum} – 2 \cdot \text{minAbs}answer=absSum−2⋅minAbs

Case C: There is at least one zero

A zero is special because flipping it doesn’t change it:

• 0 * (-1) = 0

So if a zero is adjacent (or can be made adjacent through sequences), you can use it to flip the sign of a single element without “paying” a second sign flip effectively affecting parity in the negative-count sense.

Practical takeaway:

• If there is a 0, you can always achieve the “all non-negative” configuration.

✅ Answer = absSum

---

Final Formula

Compute:

• absSum = Σ |a[i][j]|
• negCount = number of elements < 0
• minAbs = minimum |a[i][j]|
• hasZero = any element == 0

Then:

• If negCount is even or hasZero is true → absSum
• Else → absSum - 2 * minAbs

---

Algorithm

1. Initialize:
   • absSum = 0
   • negCount = 0
   • minAbs = +∞
   • hasZero = false
2. For each value x in the matrix:
   • absSum += abs(x)
   • if x < 0: negCount++
   • if x == 0: hasZero = true
   • minAbs = min(minAbs, abs(x))
3. Apply the rule above and return.

---

Complexity

• Time: O(n^2) (one pass through the matrix)
• Space: O(1)
• Use 64-bit integer (long long / long / Python int) because sums can be large.

---

Python Implementation

class Solution:
    def maxMatrixSum(self, matrix):
        abs_sum = 0
        neg_count = 0
        min_abs = float("inf")
        has_zero = False

        for row in matrix:
            for x in row:
                if x < 0:
                    neg_count += 1
                if x == 0:
                    has_zero = True

                ax = abs(x)
                abs_sum += ax
                min_abs = min(min_abs, ax)

        if has_zero or neg_count % 2 == 0:
            return abs_sum
        return abs_sum - 2 * min_abs

---

Common Pitfalls

• Forgetting zeros: With a zero present, odd negative parity no longer blocks you from reaching absSum.
• Using 32-bit integers: The sum of absolute values can overflow in languages like C++/Java if you use int.
• Overthinking adjacency: You don’t need to simulate operations; the parity + min-abs logic is enough.