目标
给你一个 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
思路
有一个 n x n 矩阵，每次操作可以将相邻的元素乘以 -1，执行操作任意次，求能够得到的最大方阵和。
经过观察发现，可以将任意两个元素乘以 -1，只需对路径上的每个元素执行操作，改变 (cur, next) 的符号，中间每个元素的符号都被改变了两次，即首尾元素改变了符号。
只需判断矩阵中负数的个数，如果是偶数，可以将负数全部变为相反数；如果是奇数，则需要找到最小的非负数，将其变为负数，其余元素全部变为非负数。
代码
/**
* @date 2026-01-05 9:07
*/
public class MaxMatrixSum1975 {
public long maxMatrixSum(int[][] matrix) {
long res = 0L;
int negativeCnt = 0;
int min = Integer.MAX_VALUE;
for (int[] row : matrix) {
for (int col : row) {
res += Math.abs(col);
min = Math.min(min, Math.abs(col));
if (col < 0) {
negativeCnt++;
}
}
}
if (negativeCnt % 2 == 1) {
res -= 2 * min;
}
return res;
}
}
性能
