Maximum Matrix Sum

medium greedy matrix parity

Problem

You are given an n × n integer matrix. Any number of times you may pick two adjacent cells (sharing a border) and multiply both by −1. Maximize the sum of all elements and return that maximum sum.

Flipping a pair preserves the parity of the negative count, and a sign can be shuttled between any two cells through a chain of adjacent flips. So the only thing that truly matters is whether the number of negatives is even or odd, and the smallest absolute value in the grid.

Inputmatrix = [[1,-1],[-1,1]]

Output4

Two negatives (even). Flip the first row, then the first column; every cell becomes +1, giving sum 4 = |1|+|−1|+|−1|+|1|.

matrix (rows separated by ; values by ,)

def maxMatrixSum(matrix):
    total = 0          # sum of absolute values
    negatives = 0      # how many cells are negative
    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))
    if negatives % 2 == 0:
        return total              # pair up every negative
    return total - 2 * min_abs    # one negative must stay

function maxMatrixSum(matrix) {
  let total = 0;          // sum of absolute values
  let negatives = 0;      // how many cells are negative
  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));
    }
  }
  if (negatives % 2 === 0) return total;       // pair up every negative
  return total - 2 * minAbs;                   // one negative must stay
}

long maxMatrixSum(int[][] matrix) {
    long total = 0;          // sum of absolute values
    int negatives = 0;       // how many cells are negative
    int minAbs = Integer.MAX_VALUE;
    for (int[] row : matrix) {
        for (int v : row) {
            total += Math.abs(v);
            if (v < 0) negatives++;
            minAbs = Math.min(minAbs, Math.abs(v));
        }
    }
    if (negatives % 2 == 0) return total;        // pair up every negative
    return total - 2L * minAbs;                  // one negative must stay
}

long long maxMatrixSum(vector<vector<int>>& matrix) {
    long long total = 0;     // sum of absolute values
    int negatives = 0;       // how many cells are negative
    int minAbs = INT_MAX;
    for (auto& row : matrix) {
        for (int v : row) {
            total += abs(v);
            if (v < 0) negatives++;
            minAbs = min(minAbs, abs(v));
        }
    }
    if (negatives % 2 == 0) return total;        // pair up every negative
    return total - 2LL * minAbs;                 // one negative must stay
}

Explanation

The key insight is figuring out which sign patterns are reachable. A single operation flips two adjacent cells, so each operation changes the number of negatives by −2, 0, or +2. The parity of the negative count never changes.

By chaining flips along a path of adjacent cells, a negative sign can be carried from any cell to any other cell (the intermediate flips cancel out). This means we can freely relocate negatives, as long as their count's parity stays the same.

If the number of negatives is even, we can pair them up and cancel every one of them, turning the whole grid positive. The answer is simply the sum of absolute values — the largest possible total.

If the number of negatives is odd, one stubborn negative can never be removed. To lose as little as possible, we park that negative on the cell with the smallest absolute value min_abs. Its contribution flips from +min_abs to −min_abs, a drop of 2 × min_abs, so the answer is total − 2 × min_abs.

One linear pass over all n² cells collects everything: total (sum of |values|), negatives (the parity), and min_abs. Notice a value of 0 behaves like a free negative — if any cell is 0, min_abs = 0 and the odd case costs nothing.

Time: O(n²) Space: O(1)