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
- A single operation flips the sign of two adjacent cells, so along a path of operations you can move a negative sign anywhere.
- Consequently the parity of the number of negative cells is invariant: it can never change by an odd amount.
- If the count of negatives is even, every cell can be made positive and the answer is the sum of absolute values.
- 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_absof 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.