M1975.最大方阵和

greedy, https://leetcode.cn/problems/maximum-matrix-sum/

给你一个 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].length
2 <= n <= 250
-10^5 <= matrix[i][j] <= 10^5

这道题目可以通过观察操作的性质来得出结论。

核心思路

操作的本质：你可以选择两个相邻的元素并同时改变它们的符号。
- 如果你想改变两个不相邻元素 $A$ 和 $B$ 的符号，你可以通过一条路径连接它们。例如路径为 $A - C - B$ ：
  - 翻转 $(A, C) \to (- A, - C)$
  - 翻转 $(C, B) \to (- C \times - 1, - B) = (C, - B)$
  - 最终结果是 $A$ 和 $B$ 变号了，而中间的 $C$ 符号不变。
- 结论：你可以翻转矩阵中任意两个元素的符号，而不影响其他元素。
负号数量的奇偶性：每次操作都会同时改变两个元素的符号：
- 两个负数 $\to$ 两个正数（负号减少 2 个）
- 两个正数 $\to$ 两个负数（负号增加 2 个）
- 一正一负 $\to$ 一负一正（负号数量不变）
- 结论：矩阵中负号总数的奇偶性是永远不会改变的。
贪心策略：
- 如果矩阵中有偶数个负数，你可以通过成对翻转，把所有的负数都变成正数。此时最大和就是所有元素绝对值的总和。
- 如果矩阵中有奇数个负数，无论你怎么翻转，最终至少会留下一个负数。为了使总和最大，我们应该让那个绝对值最小的元素保留负号。

算法步骤

遍历整个矩阵。
计算所有元素绝对值的总和 total_sum。
统计负数的个数 neg_count。
找到矩阵中绝对值最小的元素 min_abs。
判断负数个数：
- 如果 neg_count 是偶数，返回 total_sum。
- 如果 neg_count 是奇数，返回 total_sum - 2 * min_abs（减去两次是因为在 total_sum 中我们加上了它的绝对值，现在要把加上的减掉，再把它作为负数减去）。

代码实现

python

class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        total_sum = 0
        neg_count = 0
        min_abs = float('inf')
        
        for row in matrix:
            for val in row:
                abs_val = abs(val)
                total_sum += abs_val
                if val < 0:
                    neg_count += 1
                if abs_val < min_abs:
                    min_abs = abs_val
        
        # 如果负数个数为偶数，可以全部抵消变成正数
        if neg_count % 2 == 0:
            return total_sum
        # 如果负数个数为奇数，必须留下一个绝对值最小的作为负数
        else:
            return total_sum - 2 * min_abs

复杂度分析

时间复杂度： $O (n^{2})$ ，其中 $n$ 是方阵的边长。我们需要遍历矩阵中的每一个元素一次。
空间复杂度： $O (1)$ ，只使用了常数级别的额外空间。

M1975.最大方阵和 ​

M1975.最大方阵和