#1975

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum Matrix Sum

Maximize the sum of an n x n integer matrix using row and column negation operations efficiently with a greedy approach.

array greedy matrix

Problem Statement

Given an n x n integer matrix, you can multiply any row or column by -1 any number of times to maximize the sum of all elements. Each row or column operation affects all elements in that line simultaneously.

Two elements are adjacent if they share a side, but the operation is global on rows or columns. Return the maximum sum achievable after performing any sequence of these operations.

Examples

Example 1

Input: matrix = [[1,-1],[-1,1]]

Output: 4

We can follow the following steps to reach sum equals 4:

Multiply the 2 elements in the first row by -1.
Multiply the 2 elements in the first column by -1.

Example 2

Input: matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]

Output: 16

We can follow the following step to reach sum equals 16:

Multiply the 2 last elements in the second row by -1.

Constraints

n == matrix.length == matrix[i].length
2 <= n <= 250
-105 <= matrix[i][j] <= 105

Solution Approach

Greedy Flip Strategy

Count all negative numbers and compute total absolute sum. If negatives are even, flip rows or columns to make all numbers positive. If odd, leave the smallest absolute value negative to maximize sum.

Invariant Tracking

Maintain the parity of negative numbers throughout flips. The minimal absolute value element determines whether the final sum should subtract twice its value if an odd negative count remains.

Implementation Details

Iterate through the matrix once to sum absolute values and track minimal element. Apply flips conceptually; no need to modify the matrix. Return total sum adjusted for final parity.

Complexity Analysis

Metric	Value
Time	O(n \times m)
Space	O(1)

Time complexity is O(n^2) for scanning all elements once. Space complexity is O(1) since no extra storage beyond counters is needed.

What Interviewers Usually Probe

You start considering flipping rows versus columns for sum optimization.
You mention counting negative numbers and tracking minimal absolute values.
You reason about parity of negative counts affecting the final sum.

Common Pitfalls or Variants

Common pitfalls

Neglecting to track the minimal absolute value when negatives are odd.
Flipping individual elements instead of entire rows or columns.
Miscounting the number of negative elements affecting the parity check.

Follow-up variants

Consider maximizing sum in a rectangular m x n matrix instead of square.
Allow only row flips or only column flips as a variant constraint.
Minimize matrix sum using the same flip operations as a twist.

FAQ

What is the Maximum Matrix Sum problem about?

It is about maximizing the total sum of an n x n matrix by flipping entire rows or columns using a greedy strategy and parity check.

How does the greedy choice apply here?

Flip rows or columns to convert negatives to positives while tracking minimal values and parity to ensure maximal sum.

What if the number of negative elements is odd?

Leave the smallest absolute value element negative to ensure the final sum is maximized.

Can this approach handle large matrices efficiently?

Yes, the algorithm runs in O(n^2) time and O(1) space, scanning the matrix once without extra storage.

Does GhostInterview show the exact operations to apply?

It focuses on sum impact, parity, and minimal element tracking rather than enumerating every flip, guiding efficient decision-making.

terminal

Solution

Solution 1: Greedy

If there is a zero in the matrix, or the number of negative numbers in the matrix is even, then the maximum sum is the sum of the absolute values of all elements in the matrix.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        mi = inf
        s = cnt = 0
        for row in matrix:
            for x in row:
                cnt += x < 0
                y = abs(x)
                mi = min(mi, y)
                s += y
        return s if cnt % 2 == 0 else s - mi * 2

Continue Practicing

#2132 stamping the grid #1727 largest submatrix with rearrangements #1605 find valid matrix given row and column sums