LeetCode 题解工作台
最大方阵和
给你一个 n x n 的整数方阵 matrix 。你可以执行以下操作 任意次 ： 选择 matrix 中 相邻 两个元素，并将它们都 乘以 -1 。 如果两个元素有 公共边 ，那么它们就是 相邻 的。 你的目的是 最大化 方阵元素的和。请你在执行以上操作之后，返回方阵的 最大 和。 示例 1： 输入…
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
如果矩阵中存在零，或者矩阵中负数的个数为偶数，那么最大和就是矩阵中所有元素的绝对值之和。 否则，说明矩阵中有奇数个负数，最终一定会剩下一个负数，我们选择绝对值最小的数，将其变为负数，这样可以使得最终的和最大。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个 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].length2 <= n <= 250-105 <= matrix[i][j] <= 105
解题思路
方法一：贪心
如果矩阵中存在零，或者矩阵中负数的个数为偶数，那么最大和就是矩阵中所有元素的绝对值之和。
否则，说明矩阵中有奇数个负数，最终一定会剩下一个负数，我们选择绝对值最小的数，将其变为负数，这样可以使得最终的和最大。
时间复杂度 ，其中 和 分别是矩阵的行数和列数。空间复杂度 。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n^2) for scanning all elements once. Space complexity is O(1) since no extra storage beyond counters is needed. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
You start considering flipping rows versus columns for sum optimization.
- question_mark
You mention counting negative numbers and tracking minimal absolute values.
- question_mark
You reason about parity of negative counts affecting the final sum.
常见陷阱
外企场景- error
Neglecting to track the minimal absolute value when negatives are odd.
- error
Flipping individual elements instead of entire rows or columns.
- error
Miscounting the number of negative elements affecting the parity check.
进阶变体
外企场景- arrow_right_alt
Consider maximizing sum in a rectangular m x n matrix instead of square.
- arrow_right_alt
Allow only row flips or only column flips as a variant constraint.
- arrow_right_alt
Minimize matrix sum using the same flip operations as a twist.