题目描述
思路解析动画文字版
记牢这句话:符号翻转能把任意两个格子一起翻。没有 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题