难度: Medium
给你一个 n x n 的整数方阵 matrix 。你可以执行以下操作 任意次 ：
matrix 中 相邻 两个元素，并将它们都 乘以 -1 。如果两个元素有 公共边 ，那么它们就是 相邻 的。
你的目的是 最大化 方阵元素的和。请你在执行以上操作之后，返回方阵的 最大 和。
示例 1：
输入：matrix = [[1,-1],[-1,1]] 输出：4 解释：我们可以执行以下操作使和等于 4 ： - 将第一行的 2 个元素乘以 -1 。 - 将第一列的 2 个元素乘以 -1 。
示例 2：
输入：matrix = [[1,2,3],[-1,-2,-3],[1,2,3]] 输出：16 解释：我们可以执行以下操作使和等于 16 ： - 将第二行的最后 2 个元素乘以 -1 。
提示：
n == matrix.length == matrix[i].length2 <= n <= 250-105 <= matrix[i][j] <= 105运行时间: 83 ms
内存: 23.8 MB
class Solution:
def maxMatrixSum(self, matrix: List[List[int]]) -> int:
"""
每一行: 如果负数个数为偶数, 可以都变成正数
如果负数个数为奇数, 可以转换到只剩下一个负数, 那么选者绝对值最小的那个数成为负数, 记录下负数的坐标
统计:
每一行, 要么全是正数, 要么至多有一个负数
我们可以把每行的负数都调整到同一列上, 这样如果该列负数的个数为偶数, 那么我们在列上进行转换, 可以都转换为正数
否则,我们就只能转换到只剩下一个最小的负数了
综上所述, 最终 整个矩阵中只有一个负数, 我们将选择矩阵中绝对值最小的那个数成为负数
"""
n = len(matrix)
cnt = 0 # 记录转换后留有一个负数的行数
sm = 0 # 记录所有数字的绝对值累加和
mn = abs(matrix[0][0]) # 记录绝对值最小的数
for i in range(n):
neg_cnt = 0
for num in matrix[i]:
x = abs(num)
sm += x
if x < mn:
mn = x
if num < 0:
neg_cnt += 1
if neg_cnt % 2 == 1:
cnt += 1
return sm if cnt % 2 == 0 else sm - mn * 2
这道题目的思路是通过矩阵的行和列的操作，使得矩阵中尽可能多的元素变为正数，从而最大化矩阵元素的和。首先遍历矩阵的每一行，统计每行中负数的个数。如果负数的个数为偶数，那么可以通过翻转操作使得该行所有元素都变为正数。如果负数的个数为奇数，那么可以翻转除了一个绝对值最小的负数以外的所有负数，使得该行只剩下一个负数。接着，统计转换后留有一个负数的行数，如果这个数为偶数，那么可以通过列的翻转操作，使得所有行都变为正数。如果这个数为奇数，那么最终会剩下一个负数，我们选择矩阵中绝对值最小的那个数成为负数。最后，返回矩阵所有元素的绝对值之和，如果有剩余的负数，则减去该负数的两倍。
时间复杂度: O(n^2)
空间复杂度: O(1)
class Solution:
def maxMatrixSum(self, matrix: List[List[int]]) -> int:
n = len(matrix)
cnt = 0 # 记录转换后留有一个负数的行数
sm = 0 # 记录所有数字的绝对值累加和
mn = abs(matrix[0][0]) # 记录绝对值最小的数
for i in range(n):
neg_cnt = 0
for num in matrix[i]:
x = abs(num)
sm += x
if x < mn:
mn = x
if num < 0:
neg_cnt += 1
if neg_cnt % 2 == 1:
cnt += 1
return sm if cnt % 2 == 0 else sm - mn * 2
在解决方案中，首先遍历每一行，如果一行中负数的个数为偶数，则可以通过翻转整行使所有元素变为正数。如果负数的个数为奇数，则翻转除了一个绝对值最小的负数以外的所有负数。这样处理后，会记录下来留有一个负数的行的数量。如果这个数量为奇数，说明存在奇数行只有一个负数，此时需要通过翻转列来尝试消除多余的负数。如果数量为偶数，这表示所有行都可以被调整为全正数，无需进一步翻转列。
选择保留绝对值最小的负数是为了在后续可能需要调整该负数为正数时，影响到整体和的减少最小。因为在最终计算矩阵的总和时，如果行中负数个数的总和为奇数，我们必须保留一个负数。此时，如果保留的是绝对值最小的负数，最终从总和中减去这个负数的两倍（因为先前已经以正数加入总和一次），对总和的影响最小。
如果矩阵中所有元素均为负数，在每行执行翻转可以使所有元素变为正数。由于负数的个数在每行都是奇数，翻转除了绝对值最小的负数以外的所有负数后，每行都将剩下一个负数。然后，可以通过列的翻转来尝试减少剩余负数的总数。最终可能需要保留一个绝对值最小的负数，以保证总和最大化。因此，特殊翻转策略主要涉及先行后列地尽可能转正更多的数，最后可能保留一个最小的负数。
在本算法中，翻转顺序主要是先对行进行处理，后对列进行处理。这是因为行翻转是基于每行的负数计数来决定的，而列翻转是用来调整那些仍然保留一个负数的行的数量。翻转顺序对结果有影响，因为先行后列的方式可以先局部优化每行，然后全局调整列，以确保最终结果的最大化。如果先进行列翻转可能会破坏行的最优状态，导致无法达到最大的总和。