⚡Flashcard Drill➔
NeetCode #814LC-1975MediumGreedy
← Back to All Problems

#814 · #1975 · Maximum Matrix Sum(最大方阵和)

📌 Problem Statement & Constraints

You are given an m x n integer matrix. An operation chooses two adjacent cells (sharing a side) and multiplies both by -1. You may apply the operation any number of times. Return the maximum possible sum of the matrix. Constraints: 2 <= m, n <= 250, -10^5 <= matrix[i][j] <= 10^5.

💡 Core Algorithmic Approaches

  1. A single operation flips the sign of two adjacent cells, so along a path of operations you can move a negative sign anywhere.
  2. Consequently the parity of the number of negative cells is invariant: it can never change by an odd amount.
  3. If the count of negatives is even, every cell can be made positive and the answer is the sum of absolute values.
  4. If the count is odd, exactly one cell must remain negative; sacrifice the smallest absolute value, giving sum(abs) - 2 * min(abs).

💻 Benchmark Python3 Implementation

class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        total = 0
        negatives = 0
        min_abs = float("inf")
        for row in matrix:
            for v in row:
                if v < 0:
                    negatives += 1
                total += abs(v)
                min_abs = min(min_abs, abs(v))
        if negatives % 2 == 0:
            return total                    # all cells can be made positive
        return total - 2 * min_abs          # one cell stays negative

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): a single pass over the matrix.
💾 Space Complexity
O(1): three scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the parity invariant: flipping two signs changes the negative count by -2, 0, or +2, so its parity is fixed.
  • Handling zeros: a zero has absolute value 0, so if a zero exists the odd case still costs nothing; the formula naturally gives total - 0.
  • Trying to fix each negative locally: signs can be relocated along paths, so the only real constraint is the global parity.
  • Computing the sacrifice as 2 * min_abs of the negatives only: the minimum must be taken over all cells, including positives, when the odd negative count forces a positive cell to absorb the sign.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems