Maximum Matrix Sum

Medium
902.

Maximum Matrix Sum

Maximum Matrix Sum is a medium coding problem on arrays, greedy and matrix, asked in Amazon, Google and Zoho interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} matrix
 * @return {number}
 */
var maxMatrixSum = function(matrix) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Matrix Sum — Solution in Python, Java & C++

Maximum Matrix Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and greedy.

Maximum Matrix Sum is a medium coding problem on arrays, greedy and matrix, asked in Amazon, Google and Zoho interviews.

  • Difficulty: Medium
  • Topics: Arrays, Greedy, Matrix
  • Asked at: Amazon, Google, Zoho
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Maximum Matrix Sum

  1. Hint 1

    Each operation flips two signs, so the parity of the number of negative entries never changes.

  2. Hint 2

    With an even number of negatives, every sign can be cleared and the answer is the sum of absolute values.

  3. Hint 3

    With an odd number, exactly one entry must stay negative — make it the smallest absolute value.

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

Java

public static int maxMatrixSum(int[][] matrix) {
    long sum = 0;
    int negs = 0, mn = Integer.MAX_VALUE;
    for (int[] row : matrix) {
        for (int v : row) {
            int a = Math.abs(v);
            sum += a;
            if (v < 0) negs++;
            mn = Math.min(mn, a);
        }
    }
    return (int) (negs % 2 == 0 ? sum : sum - 2L * mn);
}

C++

int maxMatrixSum(vector<vector<int>>& matrix) {
    long long sum = 0;
    int negs = 0, mn = INT_MAX;
    for (auto& row : matrix) {
        for (int v : row) {
            int a = abs(v);
            sum += a;
            if (v < 0) negs++;
            mn = min(mn, a);
        }
    }
    return (int) (negs % 2 == 0 ? sum : sum - 2LL * 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms