DSA problem
Maximum Matrix Sum
You are given an n x n integer matrix. You can do the following operation any number of times: choose any two adjacent elements of matrix and multiply each of them by -1. Two elements are considered adjacent if and only if they share a border. Your goal is to maximize the summation of the matrix's elements. Return the maximum sum of the matrix's elements using the operation mentioned above.
A brute-force search over sign assignments has 2^(n*n) possibilities, hopeless beyond tiny grids. The breakthrough comes from analyzing what one operation actually does: flipping two adjacent cells' signs preserves the parity of "number of negatives" in the entire matrix and lets us move a negative sign freely to any other cell via a path of flips.
That means the reachable sign configurations are exactly those whose count of negatives has the same parity as the original. So the question reduces to: with that parity constraint, what is the maximum sum? Clearly we want every cell positive when possible, contributing sum(|a[i][j]|). If the parity of negatives is even, we can drive every cell positive — answer is sum(|a[i][j]|). If the parity is odd, exactly one cell must remain negative, and we should pick the one with the smallest absolute value to minimize the deduction.
So the algorithm is a single pass: compute the total absolute sum, count negatives, and track the minimum absolute value. If negatives count is even, return the absolute sum; otherwise return absoluteSum - 2 * minAbs (subtracting the min absolute value twice: once to remove it from the positive contribution, once to add its negation). Time O(n^2), space O(1).
Examples
matrix = [[1,-1],[-1,1]]4matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]16matrix = [[0,-1]]1Constraints
- n == matrix.length == matrix[i].length
- 2 <= n <= 250
- -10^5 <= matrix[i][j] <= 10^5
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.