题目描述
思路解析
一句话答案：LeetCode 1975 最大方阵和：相邻两格能同时翻号，等价于任意两格随便翻，于是最大和只由负数个数的奇偶决定——偶数全取绝对值之和，奇数再减去 2 乘最小绝对值，一遍扫描 O(n²)。
方阵里翻来翻去，到底求的是什么最大值
给一个 n 行 n 列的整数方阵 matrix。一次操作能挑相邻、也就是有公共边的两个格子，把它俩同时乘以 -1，操作次数不限。求折腾到最后，方阵所有元素加起来最大能是多少。题面第二个例子 matrix=[[1,2,3],[-1,-2,-3],[1,2,3]] 答案是 16，翻掉正中那行三个负数即可。
盯着「相邻两格」去搬负号，越搬越乱
负数散落各处，顺着操作去搬就麻烦：哪两个相邻负数凑一块翻成正、落单的再沿哪条路挪去抵消，顺序随负号变多爆炸式增长，方阵稍大就理不清。力气全花在「怎么搬」，可最大和只关心搬完剩下什么。
只能翻相邻两格，为什么等于任意两格随便翻
松开「相邻」这层表象：想同时翻两个不挨着的格子，只要沿一条连起它俩的路径逐段翻相邻两个，中间格子被翻两次抵消复原，最后只有路径两端真的变号。任意两个格子都能被同时变号。
再数一层：每次操作恰好改变两个符号，负号总个数只会加二、减二或不变，奇偶从头到尾锁死。负数是奇数个就永远奇数个、偶数个就永远偶数个。两条合起来，整道题塌缩成一个问题：负数个数是奇是偶。
偶数全清成正，奇数把负号丢给绝对值最小的格
先不看正负，每个数的绝对值都是想收进总和的那份。负数个数是偶数时，两两配对、每对同时翻正，一个负号都不剩，答案就是所有元素绝对值之和。
是奇数时，配到最后必剩一个负号清不掉，得让某个格子背着。一个本该加绝对值 a 的格子被压成负，总和从 +a 掉到 -a，损失 2a。要让损失最小，就把负号丢给绝对值最小的格子，答案是绝对值之和减去 2 乘最小绝对值。这个格子原本正负都无所谓；方阵里有 0 时，负号塞给它损失为零，绝对值之和照拿。
题面例二一遍扫描得 16
拿题面第二个例子走一遍。一次扫过九个格子，同时攒三样东西：绝对值之和 s、负数个数 cnt、最小绝对值 mi。
第一行 1、2、3 是正数，s 到 6，cnt 仍 0，mi 刷到 1。第二行 -1、-2、-3，绝对值 1、2、3 接着加，s 到 12，三个负数把 cnt 顶到 3，mi 碰到 1 不再更小。第三行再加 1、2、3，s 到 18，cnt 不动，mi 仍是 1。扫完 s=18、cnt=3、mi=1；cnt 是奇数，答案 = 18 − 2×1 = 16，与答案一致。第一个例子 [[1,-1],[-1,1]] 绝对值之和 4、负数 2 个是偶数，直接返回 4。
一遍扫完 O(n²)，真正会栽的是溢出和那个 0
复杂度上，n 乘 n 个元素只扫一遍，每格做取绝对值、比大小、累加这些常数操作，时间 O(n²)；只留 s、cnt、mi 三个标量、不排序不开数组，空间 O(1)。
两个地方最容易栽。求和变量别用 32 位整数——n 到 250、单个绝对值到十万，和最坏能到六十多亿，早超过 int 上限，得 C++ 用 long long、Java 用 long，Python 无此上限。另一处是 0：它的绝对值是 0，天然就是最小绝对值，于是负数个数即便为奇，把负号塞给它损失也是零，公式原样覆盖、无需特判。反过来，整张方阵全是负数、但个数为偶时，也照样两两翻正、一个不剩。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这句话:符号翻转能把任意两个格子一起翻。没有 0 时,真正被卡死的只有负数个数的奇偶,偶数能全清成正、奇数得留一个负号;有 0 时多出的负号可被 0 吸收,相当于最小绝对值是 0。下面一遍扫描,把绝对值之和、负数个数、最小绝对值三样东西同时数出来。
原始方阵 · 红色是负数：先看清这个 3 乘 3 的方阵。标红的三个格子是负数,分别是 (0,1) 的 -3,(1,0) 的 -4,(2,1) 的 -7,一共三个负数。其余都是正数。我们要做的是一遍扫描,把每个格子的绝对值加起来,同时数清负数有几个、绝对值最小的是多少。
读第 1 格 (0,0) = 2：扫到第 1 个格子 (0,0),它的值是 2,是个正数,绝对值是 2。先把它举起来看清楚,下一拍再把它算进三个累计量里。
结算 (0,0) · 和 = 2：把绝对值 2 加进总和,和从 0 变成 2。它是正数,负数个数还是 0。它的绝对值 2 比之前更小,最小绝对值刷新成 2。这一格结算完毕,给它上色收进已扫的行列。
读第 2 格 (0,1) = -3：扫到第 2 个格子 (0,1),它的值是 -3,是个负数,绝对值是 3。先把它举起来看清楚,下一拍再把它算进三个累计量里。
结算 (0,1) · 和 = 5：把绝对值 3 加进总和,和从 2 变成 5。它是负数,负数个数加到 1。最小绝对值仍是 2。这一格结算完毕,给它上色收进已扫的行列。
读第 3 格 (0,2) = 5：扫到第 3 个格子 (0,2),它的值是 5,是个正数,绝对值是 5。先把它举起来看清楚,下一拍再把它算进三个累计量里。
结算 (0,2) · 和 = 10：把绝对值 5 加进总和,和从 5 变成 10。它是正数,负数个数还是 1。最小绝对值仍是 2。这一格结算完毕,给它上色收进已扫的行列。
读第 4 格 (1,0) = -4：扫到第 4 个格子 (1,0),它的值是 -4,是个负数,绝对值是 4。先把它举起来看清楚,下一拍再把它算进三个累计量里。
结算 (1,0) · 和 = 14：把绝对值 4 加进总和,和从 10 变成 14。它是负数,负数个数加到 2。最小绝对值仍是 2。这一格结算完毕,给它上色收进已扫的行列。
读第 5 格 (1,1) = 1：扫到第 5 个格子 (1,1),它的值是 1,是个正数,绝对值是 1。先把它举起来看清楚,下一拍再把它算进三个累计量里。
结算 (1,1) · 和 = 15：把绝对值 1 加进总和,和从 14 变成 15。它是正数,负数个数还是 2。它的绝对值 1 比之前更小,最小绝对值刷新成 1。这一格结算完毕,给它上色收进已扫的行列。
读第 6 格 (1,2) = 6：扫到第 6 个格子 (1,2),它的值是 6,是个正数,绝对值是 6。先把它举起来看清楚,下一拍再把它算进三个累计量里。
结算 (1,2) · 和 = 21：把绝对值 6 加进总和,和从 15 变成 21。它是正数,负数个数还是 2。最小绝对值仍是 1。这一格结算完毕,给它上色收进已扫的行列。
读第 7 格 (2,0) = 8：扫到第 7 个格子 (2,0),它的值是 8,是个正数,绝对值是 8。先把它举起来看清楚,下一拍再把它算进三个累计量里。
结算 (2,0) · 和 = 29：把绝对值 8 加进总和,和从 21 变成 29。它是正数,负数个数还是 2。最小绝对值仍是 1。这一格结算完毕,给它上色收进已扫的行列。
读第 8 格 (2,1) = -7：扫到第 8 个格子 (2,1),它的值是 -7,是个负数,绝对值是 7。先把它举起来看清楚,下一拍再把它算进三个累计量里。
结算 (2,1) · 和 = 36：把绝对值 7 加进总和,和从 29 变成 36。它是负数,负数个数加到 3。最小绝对值仍是 1。这一格结算完毕,给它上色收进已扫的行列。
读第 9 格 (2,2) = 2：扫到第 9 个格子 (2,2),它的值是 2,是个正数,绝对值是 2。先把它举起来看清楚,下一拍再把它算进三个累计量里。
结算 (2,2) · 和 = 38：把绝对值 2 加进总和,和从 36 变成 38。它是正数,负数个数还是 3。最小绝对值仍是 1。这一格结算完毕,给它上色收进已扫的行列。
扫描完毕 · 三个量都定了：九个格子全部扫完。绝对值之和是 38,负数个数是 3,绝对值最小的是 1,就在中心那个正数格 (1,1)。三个数据齐了,接下来只看一件事:负数个数是奇是偶。
负数个数 = 3,是奇数：负数个数是 3,是个奇数。这个例子里没有 0,前面说过每次操作翻两个符号,非零格子里负号的奇偶变不了,奇数就永远是奇数。所以无论怎么折腾,最后至少要剩一个负号,清不干净。既然躲不掉,那就想办法让这一个负号带来的损失尽可能小。
把唯一的负号丢给绝对值最小的 (1,1)：三个负号里,通过翻转可以把其中两个配对清成正,剩下这一个负号,我们不给别人,专门丢给绝对值最小的格子 (1,1)。注意它原本是正数 1,现在被牺牲成 -1。为什么选它,因为一个本该加 1 的格子变成减 1,一来一回损失是 2 乘 1,这个损失在所有格子里最小。
最大方阵和 = 36：最终布局:八个格子都是正的,只有中心 (1,1) 留成 -1。总和等于绝对值之和 38 减去被牺牲的那 2 乘 1,也就是 38 减 2,等于 36。这就是这个方阵能达到的最大和。
边界想清:偶数负号全翻正、有 0 时奇数也无损失、全负但个数为偶照样全翻正。
面试重点:奇偶决定能否清零、和要用 long、注意 0 的存在、时间 O(n 平方) 空间 O(1)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def maxMatrixSum(self, matrix: List[List[int]]) -> int: mi = inf s = cnt = 0 for row in matrix: for x in row: cnt += x < 0 y = abs(x) mi = min(mi, y) s += y return s if cnt % 2 == 0 else s - mi * 2复杂度
- 时间：O(n²)，n 行 n 列共 n 平方个元素,只需一遍扫描,每个元素做的是取绝对值、比较、累加这些常数操作,总量随元素个数线性增长,对边长 n 就是平方级
- 空间：O(1)，只用了 s、cnt、mi 这三个标量,不随方阵规模增长。没有排序、没有额外数组,是货真价实的常数空间
易错点
面试追问把动画讲成自己的话
追问这题的贪心结论怎么一句话说清?
追问实现时最容易忽略的细节是什么?
追问时间和空间复杂度各是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
到达目的地的方案数
LeetCode 1976 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题