# Maximum Matrix Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-matrix-sum)
Canonical: https://scaleengineer.com/dsa/problems/maximum-matrix-sum
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Matrix
**Companies:** [Honeywell](https://scaleengineer.com/companies/honeywell)
---
## Problem
You are given an `n x n` integer `matrix`. You can do the following operation **any** number of times:

* Choose any two **adjacent** elements of `matrix` and **multiply** each of them by `-1`.

Two elements are considered **adjacent** if and only if they share a **border**.

Your goal is to **maximize** the summation of the matrix's elements. Return _the **maximum** sum of the matrix's elements using the operation mentioned above._

**Example 1:**

![](https://assets.glich.co/dsa/maximum-matrix-sum/image0.png) 

**Input:** matrix = [[1,-1],[-1,1]]
**Output:** 4
**Explanation:** 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:**

![](https://assets.glich.co/dsa/maximum-matrix-sum/image1.png) 

**Input:** matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]
**Output:** 16
**Explanation:** 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`

# Approaches
## Multi-Pass Approach with Parity Check
This approach is based on the key observation that any two elements in the matrix can have their signs flipped together. This is because an operation on adjacent cells `(a, b)` can be combined with an operation on `(b, c)` to flip `a` and `c`, leaving `b` unchanged. This implies we can move a pair of sign flips to any two cells. Consequently, the parity of the count of negative numbers is an invariant. We can make all numbers positive if and only if the initial count of negative numbers is even. If it's odd, one number must remain negative. To maximize the sum, this should be the number with the smallest absolute value. A zero in the matrix allows us to flip any single number's sign (by pairing it with the zero), effectively changing the parity and allowing all numbers to become non-negative. This approach calculates the necessary components in separate passes over the matrix.
**Time:** O(N*N). We iterate through the N x N matrix up to three times. Since N is the side length of the matrix, the total number of cells is N*N. Each pass takes O(N*N) time, so the total time complexity is O(N*N). · **Space:** O(1). We only use a few variables to store the counts, sums, and flags, which does not depend on the input matrix size.
**Pros:** The logic is correct and guaranteed to find the maximum sum.; The separation of passes makes the purpose of each part of the code very explicit and easy to follow.
**Cons:** Less efficient than a single-pass solution as it traverses the matrix multiple times.; The code is slightly more verbose due to the separated loops.
### Explanation
This method systematically gathers the required information by iterating over the matrix multiple times. Each pass has a distinct responsibility, making the logic clear and separated.

First, we determine the parity of negative numbers and the existence of a zero. Then, we calculate the total potential sum by summing up all absolute values. Finally, if necessary, we make a third pass to find the minimum absolute value to calculate the penalty for having an odd number of negatives without a zero. This separation of concerns can make the code easier to read and debug for some, despite being less performant.

```java
class Solution {
    public long maxMatrixSum(int[][] matrix) {
        int n = matrix.length;
        int negCount = 0;
        boolean hasZero = false;
        
        // First pass: count negatives and check for zeros
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] < 0) {
                    negCount++;
                }
                if (matrix[i][j] == 0) {
                    hasZero = true;
                }
            }
        }
        
        long totalSum = 0;
        // Second pass: calculate sum of absolute values
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                totalSum += Math.abs(matrix[i][j]);
            }
        }
        
        if (negCount % 2 == 0 || hasZero) {
            return totalSum;
        } else {
            // Third pass: find minimum absolute value
            long minAbs = Long.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    minAbs = Math.min(minAbs, Math.abs(matrix[i][j]));
                }
            }
            return totalSum - 2 * minAbs;
        }
    }
}
```
### Algorithm
- **First Pass:** Iterate through the `n x n` matrix to count the number of negative elements (`neg_count`) and to check if a zero exists (`has_zero`).
- **Second Pass:** Iterate through the matrix again to calculate the sum of the absolute values of all elements (`total_sum`).
- **Conditional Third Pass:** If `neg_count` is odd and `has_zero` is false, iterate through the matrix a third time to find the minimum absolute value among all elements (`min_abs`).
- **Result Calculation:**
  - If `neg_count` is even or `has_zero` is true, the result is `total_sum`.
  - Otherwise, the result is `total_sum - 2 * min_abs`.

## Optimal Single-Pass Approach
This approach optimizes the multi-pass method by gathering all necessary information in a single traversal of the matrix. The underlying logic is identical: the final sum depends on the parity of the negative number count. If the count is even or a zero is present, all numbers can be made non-negative, and the sum is the total of all absolute values. If the count is odd and no zeros exist, one number must remain negative. To maximize the sum, this should be the one with the smallest absolute value. By iterating through the matrix only once, we can simultaneously calculate the sum of absolute values, count negative numbers, find the minimum absolute value, and check for the presence of zeros, leading to a more efficient solution.
**Time:** O(N*N). We iterate through the N x N matrix exactly once, which is the minimum required to inspect all elements. · **Space:** O(1). We use a constant amount of extra space for our variables, regardless of the matrix size.
**Pros:** Most efficient solution with the best possible time and space complexity.; The code is concise and elegant, solving the problem with a single pass over the data.
**Cons:** The logic, while concise, combines multiple calculations into one loop, which might be slightly harder to grasp initially compared to a multi-pass approach.
### Explanation
This is the most efficient way to solve the problem. By using a single loop, we can reduce the constant factors in the time complexity, making the execution faster. We maintain several variables that are updated during the traversal: `totalSum` for the sum of absolute values, `negCount` for the count of negative numbers, `minAbs` for the minimum absolute value seen, and `hasZero` as a flag.

After iterating through all elements, we have all the information needed to make a final decision based on the same logic as the multi-pass approach. This avoids redundant iterations and represents a clean, optimal implementation.

```java
class Solution {
    public long maxMatrixSum(int[][] matrix) {
        int n = matrix.length;
        long totalSum = 0;
        int negCount = 0;
        long minAbs = Long.MAX_VALUE;
        boolean hasZero = false;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int val = matrix[i][j];
                totalSum += Math.abs(val);
                minAbs = Math.min(minAbs, Math.abs(val));
                
                if (val < 0) {
                    negCount++;
                }
                if (val == 0) {
                    hasZero = true;
                }
            }
        }

        if (negCount % 2 == 0 || hasZero) {
            return totalSum;
        } else {
            return totalSum - 2 * minAbs;
        }
    }
}
```
### Algorithm
- Initialize `total_sum = 0`, `neg_count = 0`, `min_abs = infinity`, and `has_zero = false`.
- Perform a **Single Pass** over the matrix. In each iteration, for an element `val`:
    - Add `abs(val)` to `total_sum`.
    - Update `min_abs = min(min_abs, abs(val))`.
    - If `val < 0`, increment `neg_count`.
    - If `val == 0`, set `has_zero = true`.
- After the loop, if `neg_count` is even or `has_zero` is true, return `total_sum`.
- Otherwise, return `total_sum - 2 * min_abs`.

# Solutions
### Java

```java
class Solution { public long maxMatrixSum ( int [][] matrix ) { long s = 0 ; int cnt = 0 ; int mi = Integer . MAX_VALUE ; for ( var row : matrix ) { for ( var v : row ) { s += Math . abs ( v ); mi = Math . min ( mi , Math . abs ( v )); if ( v < 0 ) { ++ cnt ; } } } if ( cnt % 2 == 0 || mi == 0 ) { return s ; } return s - mi * 2 ; } }
```

### JavaScript

```javascript
/** * @param {number[][]} matrix * @return {number} */ var maxMatrixSum =
  function (matrix) {
    let cnt = 0;
    let s = 0;
    let mi = Infinity;
    for (const row of matrix) {
      for (const v of row) {
        s += Math.abs(v);
        mi = Math.min(mi, Math.abs(v));
        cnt += v < 0;
      }
    }
    if (cnt % 2 == 0) {
      return s;
    }
    return s - mi * 2;
  };

```

### CPP

```cpp
class Solution { public: long long maxMatrixSum ( vector < vector < int >>& matrix ) { long long s = 0 ; int cnt = 0 , mi = INT_MAX ; for ( auto & row : matrix ) { for ( int & v : row ) { s += abs ( v ); mi = min ( mi , abs ( v )); cnt += v < 0 ; } } if ( cnt % 2 == 0 || mi == 0 ) return s ; return s - mi * 2 ; } };
```

### Python

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