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].length2 <= n <= 150-10000 <= matrix[i][j] <= 10000
Hints for Maximum Matrix Sum
Hint 1
Each operation flips two signs, so the parity of the number of negative entries never changes.
Hint 2
With an even number of negatives, every sign can be cleared and the answer is the sum of absolute values.
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
- Accumulate the sum of absolute values, the count of negatives, and the smallest absolute value.
- If the negative count is even, return the sum.
- 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, notminAbs: that entry swings from+minAbsto-minAbs. - The total reaches about
150² · 10^4 = 2.25 · 10^8, insideint.
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 * mnJava
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