Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Flipping adjacent pairs preserves the parity of negative signs when no zero is present. Because the grid is connected, sign changes can be passed along paths, allowing negatives to cancel in pairs. With an odd negative count, the best remaining negative has the smallest absolute value. A zero absorbs the parity restriction at no cost.

Approach

Sum all absolute values, record the minimum absolute value, and count nonpositive entries as the reference code does. Return the absolute-value sum for even parity, otherwise subtract twice the minimum. Counting zeros with negatives is harmless: whenever a zero exists, the minimum is zero and either parity branch returns the same optimum. The subtraction changes one value from positive magnitude to negative magnitude.

class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        m = len(matrix[0])
        mn = inf
        neg = 0
        res = 0

        for i in range(n):
            for j in range(m):
                curr = matrix[i][j]
                if curr <= 0:
                    neg += 1
                mn = min(mn, abs(curr))
                res += abs(curr)

        return res if neg % 2 == 0 else res - (mn * 2)

Complexity analysis

Let r and c be the matrix dimensions. Time: O(r * c). Auxiliary space: O(1).