Problem Statement in English

You’re given an n x n integer matrix matrix. You can choose any 2 adjacent elements of matrix and multiply each of them by -1 (i.e., change their sign) any number of times.

You need to return the maximum possible sum of the matrix’s elements after applying the mentioned operation any number of times.

Approach

You need to end up realizing that the only thing that matters is the number of negative elements in the matrix.

  • If there’s an even number of negative elements, you can make them all positive.
  • If there’s an odd number of negative elements, you can make all but one positive. In this case, you want to minimize the impact of the remaining negative element by choosing the one with the smallest absolute value. Remember that in the end you’ll have to subtract twice that value from the total sum (since it was added as positive initially).

And that’s it.

Solution in Python


class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        total = nneg = 0
        least = inf

        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                x = matrix[i][j]
                total += abs(x)
                least = min(least, abs(x))

                if x < 0:
                    nneg += 1

        if nneg % 2:
            total -= 2*least

        return total

Complexity

  • Time: $O(n \times m)$
    Where n is the number of rows and m is the number of columns in the matrix.

  • Space: $O(1)$
    Since we’re only using a fixed amount of extra space.

Mistakes I Made

I had to look this up :(

And we are done.