Maximum Matrix Sum

You're given an n × n integer matrix matrix. In one move you may pick any two cells that are adjacent (sharing an edge, horizontally or vertically) and multiply both of them by -1.

You can make as many moves as you like. Return the largest possible sum of all the matrix's elements.

Simulating moves is a dead end; the state space is huge. Instead, ask what a move can and cannot change.

What it can do: by flipping a chain of adjacent pairs along a path, you flip the two endpoints and every cell in between twice, which leaves the middle unchanged. So you can flip the signs of any two cells, not just neighbors. That means negatives can be paired up and cancelled anywhere in the grid.

What it can't do: each move flips two signs, so the number of negative values changes by -2, 0, or +2. Its parity never changes (ignoring zeros, which have no sign).

Put together: if the count of negatives is even, every value can end up non-negative and the answer is the sum of absolute values. If it is odd, exactly one value must stay negative, so pick the one with the smallest absolute value and subtract it twice. A zero in the grid makes this free, because the smallest absolute value is 0.

def max_matrix_sum(matrix: list[list[int]]) -> int:
    total = 0
    negatives = 0
    min_abs = float("inf")
    for row in matrix:
        for v in row:
            total += abs(v)
            if v < 0:
                negatives += 1
            min_abs = min(min_abs, abs(v))
    # Negatives can be cancelled in pairs; with an odd count, one value stays negative.
    return total if negatives % 2 == 0 else total - 2 * min_abs

function maxMatrixSum(matrix) {
  let total = 0;
  let negatives = 0;
  let minAbs = Infinity;
  for (const row of matrix) {
    for (const v of row) {
      total += Math.abs(v);
      if (v < 0) negatives++;
      minAbs = Math.min(minAbs, Math.abs(v));
    }
  }
  // Negatives can be cancelled in pairs; with an odd count, one value stays negative.
  return negatives % 2 === 0 ? total : total - 2 * minAbs;
}

Interviewers are listening for two claims, each with a one-line proof: "any two cells can be flipped together, via a path of moves" and "the parity of the negative count never changes." Say both before writing code; the code is then four lines.

Try a 2 × 2 example by hand to show the path argument, then point out the zero case explicitly.