AlgoMaster Logo

Maximum Matrix Sum

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We have an n x n matrix and can pick any two adjacent cells (sharing a border), then flip both their signs. We can repeat this as many times as we want. The goal is to maximize the total sum of all elements.

Consider what one operation does to the sign of a negative number. If cell (i, j) is negative, flipping it with a neighbor makes (i, j) positive and turns the neighbor negative. Flip that neighbor with its own neighbor and the negative sign moves again. A chain of these flips slides a single negative sign from any cell to any other cell in the matrix, since the grid is connected.

When two negatives meet at adjacent cells, flipping that pair makes both positive. Negatives therefore cancel two at a time. With an even number of negatives, every one can be paired off and cancelled, leaving all elements positive. With an odd number, one negative always remains, and the best choice is to leave it on the element with the smallest absolute value.

Key Constraints:

  • -10^5 <= matrix[i][j] <= 10^5 and up to 62,500 elements. The maximum possible sum is 62,500 x 100,000 = 6.25 x 10^9, which exceeds the range of a 32-bit integer. The accumulator must be a 64-bit type.
  • Elements can be 0. A zero counts as the smallest possible absolute value, so when an odd number of negatives forces one negative to remain, placing it on a zero costs nothing.

Approach: Greedy with Sign Counting

Intuition

The operation never changes the absolute value of any element, only its sign. So the largest sum we could ever reach is the sum of all absolute values, which happens when every element is positive. The question becomes whether the operation can drive every element positive, and if not, what the smallest unavoidable penalty is.

Two facts settle it. The first is that a single flip moves a negative sign rather than removing it: flipping a negative cell with a positive neighbor leaves one negative cell, shifted by one position. Chaining these flips slides a negative sign along any path through the connected grid, so a negative can be relocated to any cell. The second is that flipping two adjacent negatives turns both positive, removing two negatives at once.

Together these mean negatives are removed in pairs. Slide any two negatives until they are adjacent, then cancel them. With an even number of negatives, every one is paired off and the whole matrix becomes positive, giving a sum equal to the total of absolute values. With an odd number, one negative cannot be paired and must remain. To lose as little as possible, that negative belongs on the element with the smallest absolute value: keeping a value v negative instead of positive costs 2 * |v|, so the penalty is minimized by choosing the smallest |v|.

A zero is the smallest possible absolute value, so when one is present the odd-count penalty is 2 * 0 = 0. The formula below handles that case without any special branch.

The full procedure:

  • Sum the absolute values of all elements. This is the best achievable sum if every element could be made positive.
  • Track the minimum absolute value and the count of negative elements.
  • If the count of negatives is even, return the sum of absolute values.
  • If the count is odd, subtract twice the minimum absolute value: once to remove that element from the positive total and once to add it back as a negative.

Algorithm

  1. Initialize totalAbsSum = 0, minAbsValue = infinity, and negativeCount = 0.
  2. For each element in the matrix:
    • Add its absolute value to totalAbsSum.
    • Update minAbsValue if this element's absolute value is smaller.
    • If the element is negative, increment negativeCount.
  3. If negativeCount is even, return totalAbsSum.
  4. If negativeCount is odd, return totalAbsSum - 2 * minAbsValue.

Visualization and Code

Loading animation...