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.

Examples

Example 1:

$$ \begin{bmatrix} \colorbox{green}1 & \colorbox{green}{-1} \\ -1 & -1 \end{bmatrix} \implies \begin{bmatrix} \colorbox{green}{-1} & 1 \\ \colorbox{green}{-1} & 1 \end{bmatrix} \implies \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} $$

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:

$$ \begin{bmatrix} 1 & 2 & 3 \\ -1 & \colorbox{green}{-2} & \colorbox{green}{-3} \\ 1 & 2 & 3 \end{bmatrix} \implies \begin{bmatrix} 1 & 2 & 3 \\ -1 & 2 & 3 \\ 1 & 2 & 3 \end{bmatrix} $$

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.

Solution

Method 1 - Count negative elements

To solve the problem of maximising the sum of the matrix elements with the given operations, we need to address the different scenarios that the matrix might present:

  • All Positive Elements: If the matrix contains only positive numbers, the sum of all elements is the answer.
  • Even Count of Negative Elements: If there are negative numbers but their count is even, we can make all numbers positive using the adjacent -1 multiply operation, thus maximising the sum.
  • Odd Count of Negative Elements: If there is an odd number of negative elements, it is unavoidable to have one negative number left after performing the operations. Therefore, to maximise the sum, we should try to minimise the impact of this remaining negative number. This is achieved by ensuring the negative number with the smallest absolute value remains negative after the operations.

For example, consider the matrix:

10  40  -5
2  -30  20
4  -10  10

By applying the -1 multiply operations, the optimal transformation would be:

10  40   5
-2  30  20
4   10  10

Here, -2 (the smallest absolute value among the possible negatives) is left as the single negative element.

In the implementation, we calculate the sum of the absolute values of all elements, count the number of negative elements, and track the smallest absolute value. Based on the parity of the count of negative elements, we adjust the total sum:

  • Even Negative Count: Return the total sum directly.
  • Odd Negative Count: Subtract twice the smallest absolute value from the total sum to account for the necessary single negative element.

This approach ensures we achieve the highest possible sum for the matrix.

Here is the approach:

  1. Initial Summation: Calculate the initial sum of all elements in the matrix.
  2. Positive Adjustment: If we encounter negative elements that reduce the initial sum, our goal will be to convert these negative elements into positive elements by applying the operations.
  3. Odd Parity Insight: When the total count of negative elements is odd, in the optimal case, we will have a single negative element remaining after trying to convert as many negative elements into positive ones. This is because converting a pair of negative values results in a gain in sum due to double negative turning positive, whereas an odd count will leave one unpaired negative element.
  4. Minimal Absolute Impact: If there’s an odd number of negative values, the smallest absolute value among all elements should be converted back to negative (or drop from double flipping) to minimalise the negative impact on the sum due to its small value.

Code

Java
class Solution {
    public long maxMatrixSum(int[][] matrix) {
        int n = matrix.length;
        long sum = 0;
        int minAbs = Integer.MAX_VALUE;
        int negCount = 0;

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

        if (negCount % 2 != 0) {
            sum -= 2 * minAbs;
        }

        return sum;
    }
}
Python
class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        n: int = len(matrix)
        totalSum: int = 0
        minAbs: int = float('inf')
        negCount: int = 0

        for i in range(n):
            for j in range(n):
                totalSum += abs(matrix[i][j])
                if matrix[i][j] < 0:
                    negCount += 1
                minAbs = min(minAbs, abs(matrix[i][j]))

        if negCount % 2 != 0:
            totalSum -= 2 * minAbs
        
        return totalSum

Complexity

  • ⏰ Time complexity: O(n^2) since we need to iterate through an n x n matrix.
  • 🧺 Space complexity: O(1) if we do not count the input matrix as extra space.