1975.最大方阵和：脑筋急转弯

【LetMeFly】1975.最大方阵和：脑筋急转弯

力扣题目链接：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
• -105 <= matrix[i][j] <= 105

解题方法：脑筋急转弯

解这道题只需要明白：

1. 只能相邻取负 等价于 可任意两元素取负

就够了。

But Why?

知道链式效应么（名字瞎起的），[a, b, c, d]中若想实现a, d取负则可通过a, b、b, c、c, d取负的方式实现，其中中间的b、c都取负了偶数次，相当于没变。

所以我们可以得到：

• 若matrix中有偶数个负数，那么两两配对并取反，相当于全是正数！
• 若matrix中有奇数个负数，那么最终一定会有一个负数无法通过负数们“内部消化”，这个负数找一个矩阵中绝对值最小的数并让它当负数自己当正数就好了。

具体而言，遍历一遍矩阵，累加每个数的绝对值，并记下绝对值最小的数、负数的个数。

若负数有奇数个，则累加结果减去两倍最小绝对值。

• 时间复杂度$O(n^2)$，其中$SIZE(matrix)=n\times n$。
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-01-05 13:39:00
 */
typedef long long ll;
class Solution {
public:
    ll maxMatrixSum(vector<vector<int>>& matrix) {
        int minimum = 1000000;
        int cntNeg = 0;
        ll ans = 0;
        for (vector<int>& row : matrix) {
            for (int t : row) {
                ans += abs(t);
                if (t < 0) {
                    cntNeg++;
                }
                minimum = min(minimum, abs(t));
            }
        }
        if (cntNeg % 2) {
            ans -= minimum * 2;
        }
        return ans;
    }
};

/*
[[-1,0,-1],[-2,1,3],[3,2,2]]

-1 0 -1
-2 1 3
3  2 2
*/

/*
[[2,9,3],[5,4,-4],[1,7,1]]

2 9 3
5 4 -4
1 7 1

34
*/

Python

'''
LastEditTime: 2026-01-05 13:41:10
'''
from typing import List

class Solution:
    def maxMatrixSum(self, matrix: List[List[int]]) -> int:
        mini = 1000000
        cntNeg = 0
        ans = 0
        for row in matrix:
            for t in row:
                ans += abs(t)
                if t < 0:
                    cntNeg += 1
                mini = min(mini, abs(t))
        if cntNeg % 2:
            ans -= 2 * mini
        return ans

Java

/*
 * @LastEditTime: 2026-01-05 18:43:31
 */
class Solution {
    public long maxMatrixSum(int[][] matrix) {
        long ans = 0;
        int cnt = 0, min = 1000000;
        for (int[] row : matrix) {
            for (int t : row) {
                if (t < 0) {
                    cnt++;
                }
                t = Math.abs(t);
                ans += t;
                min = Math.min(min, t);
            }
        }
        if (cnt % 2 == 1) {
            ans -= 2 * min;
        }
        return ans;
    }
}

Go

/*
 * @LastEditTime: 2026-01-05 18:45:13
 */
package main

func abs1975(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

func maxMatrixSum(matrix [][]int) (ans int64) {
    cnt, mini := 0, 1000000
    for _, row := range matrix {
        for _, t := range row {
            if t < 0 {
                cnt++
            }
            t = abs1975(t)
            ans += int64(t)
            mini = min(mini, t)
        }
    }
    if cnt % 2 == 1 {
        ans -= 2 * int64(mini)
    }
    return
}

Rust

/*
 * @LastEditTime: 2026-01-05 13:43:32
 */
impl Solution {
    pub fn max_matrix_sum(matrix: Vec<Vec<i32>>) -> i64 {
        let mut ans: i64 = 0;
        let mut mini: i32 = 1000000;
        let mut cnt_neg: i32 = 0;
        for row in matrix.iter() {
            for t in row.iter() {
                ans += t.abs() as i64;
                if *t < 0 {
                    cnt_neg += 1;
                }
                mini = mini.min(t.abs());
            }
        }
        if cnt_neg % 2 == 1 {
            ans -= 2 * mini as i64;
        }
        ans
    }
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源