<p>You are given an <code>n x n</code> integer <code>matrix</code>. You can do the following operation <strong>any</strong> number of times:</p>

<ul>
	<li>Choose any two <strong>adjacent</strong> elements of <code>matrix</code> and <strong>multiply</strong> each of them by <code>-1</code>.</li>
</ul>

<p>Two elements are considered <strong>adjacent</strong> if and only if they share a <strong>border</strong>.</p>

<p>Your goal is to <strong>maximize</strong> the summation of the matrix&#39;s elements. Return <em>the <strong>maximum</strong> sum of the matrix&#39;s elements using the operation mentioned above.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/16/pc79-q2ex1.png" style="width: 401px; height: 81px;" />
<pre>
<strong>Input:</strong> matrix = [[1,-1],[-1,1]]
<strong>Output:</strong> 4
<b>Explanation:</b> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/16/pc79-q2ex2.png" style="width: 321px; height: 121px;" />
<pre>
<strong>Input:</strong> matrix = [[1,2,3],[-1,-2,-3],[1,2,3]]
<strong>Output:</strong> 16
<b>Explanation:</b> We can follow the following step to reach sum equals 16:
- Multiply the 2 last elements in the second row by -1.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == matrix.length == matrix[i].length</code></li>
	<li><code>2 &lt;= n &lt;= 250</code></li>
	<li><code>-10<sup>5</sup> &lt;= matrix[i][j] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        # Consider a row. With the operation, we can move negative symbol to the right/left until it is next to another negative one, and then use another operation to eliminate both negative ones. If there are even negatives, then we can fully eliminate negative elements. Otherwise, we can leave one. This one negative can be move left/right freely, so we can choose to keep the negative one on the element with the least abs value.
        # Consider we have done such operations on each row, we can move negatives to the same column and do the similar operations to eliminate negatives. If there are even negatives, we can fully eliminate all of them. Otherwise, we can keep the only negative at the one with the least abs value.
        # Hence, we can simply count the number of negatives. If it is even, the answer is the sum of abs of all the elements in the matrix. Otherwise, the answer is the sum minus the negative to the least abs element in the matrix.
        negs = 0
        tsum = 0
        min_abs = float("inf")
        n = len(matrix)
        for i in range(n):
            for j in range(n):
                if matrix[i][j] < 0:
                    negs += 1
                tsum += abs(matrix[i][j])
                if min_abs > abs(matrix[i][j]):
                    min_abs = abs(matrix[i][j])
        if negs % 2 == 0:
            return tsum
        else:
            return tsum - min_abs * 2
705