Maximum Matrix Sum — Medium Problem & Solution

Problem statement

One operation picks two adjacent cells (sharing a side) and multiplies both by -1. You may do this any number of times.

Return the maximum possible sum of all the matrix elements.

Example 1

Input: matrix = [[1,-1],[-1,1]]
Output: 4
Explanation: Flip each pair of negatives to get all ones.

Example 2

Input: matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]
Output: 16
Explanation: The number of negatives is even, so all of them can be cleared.

Example 3

Input: matrix = [[-1,0,-1]]
Output: 2

Constraints

• n == matrix.length == matrix[i].length
• 2 <= n <= 150
• -10000 <= matrix[i][j] <= 10000

How to solve Maximum Matrix Sum

The parity of the negative count is invariant, and it is the only obstruction. So the answer is the sum of absolute values, minus twice the smallest magnitude when that parity is odd.

Approach

1. Accumulate the sum of absolute values, the count of negatives, and the smallest absolute value.
2. If the negative count is even, return the sum.
3. Otherwise return sum - 2 · minAbs.

Why it works

Each operation changes two signs, so the negative count shifts by -2, 0 or +2 — its parity is fixed. Conversely, in a grid of at least two columns any two cells can be connected by a chain of adjacent flips, so any sign pattern with the right parity is reachable. Leaving the smallest magnitude negative costs 2 · minAbs, the cheapest possible penalty.

Complexity

• Time — O(n²)
• Space — O(1)

Pitfalls

• Zeros count as non-negative but have absolute value 0 — a single zero makes the odd case free.
• The penalty is 2 · minAbs, not minAbs: that entry swings from +minAbs to -minAbs.
• The total reaches about 150² · 10^4 = 2.25 · 10^8, inside int.

Reference solution

Python

from typing import List

def maxMatrixSum(matrix: List[List[int]]) -> int:
    total = 0
    negs = 0
    mn = float("inf")
    for row in matrix:
        for v in row:
            total += abs(v)
            if v < 0:
                negs += 1
            mn = min(mn, abs(v))
    return total if negs % 2 == 0 else total - 2 * mn

JavaScript

var maxMatrixSum = function(matrix) {
    var sum = 0, negs = 0, mn = Infinity;
    for (var i = 0; i < matrix.length; i++) {
        for (var j = 0; j < matrix[i].length; j++) {
            var v = matrix[i][j];
            var a = v < 0 ? -v : v;
            sum += a;
            if (v < 0) negs++;
            if (a < mn) mn = a;
        }
    }
    return negs % 2 === 0 ? sum : sum - 2 * mn;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium