Show problems as
Classic problem #1975MediumArrayGreedyMatrix

Maximum Matrix Sum

Real-world version: Turning Signs in Pairs on the Grid
Tracked in this browser only
Read Maximum Matrix Sum on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A square grid grid holds whole numbers, some of them below zero. One move picks two cells sharing a side and turns the sign of both of them.

Return the largest total the grid's cells can add up to after any number of moves.

Examples

Example 1

Input
grid = [[-1, 1], [1, 1]]
Output
2

One cell is below zero, and every move turns two signs, so the count of negatives can only change by two. One cell must stay negative, and the cheapest to leave is the smallest in size.

Example 2

Input
grid = [[0, -1], [1, 1]]
Output
3

One cell is below zero again, but a cell holding nothing costs nothing to leave negative, so every other cell can be made positive.

Example 3

Input
grid = [[2, -3], [5, -7]]
Output
17

Two cells are below zero, so both can be turned positive and the whole grid adds up in size.

Constraints

  • 2 <= grid.length <= 250
  • grid[i].length == grid.length
  • -10^5 <= grid[i][j] <= 10^5

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_matrix_sum(grid: list[list[int]]) -> int:
Java
public long maxMatrixSum(int[][] grid)

More on the same topics