最大方阵和 图解题解

方阵里翻来翻去，到底求的是什么最大值

给一个 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，天然就是最小绝对值，于是负数个数即便为奇，把负号塞给它损失也是零，公式原样覆盖、无需特判。反过来，整张方阵全是负数、但个数为偶时，也照样两两翻正、一个不剩。

Python

from __future__ import annotations
from 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    long long maxMatrixSum(vector<vector<int>>& matrix) {
        long long s = 0;
        int mi = 1 << 30, cnt = 0;
        for (const auto& row : matrix) {
            for (int x : row) {
                cnt += x < 0 ? 1 : 0;
                int y = abs(x);
                mi = min(mi, y);
                s += y;
            }
        }
        return cnt % 2 == 0 ? s : s - mi * 2;
    }
};

Java

import java.util.*;
class Solution {
    public long maxMatrixSum(int[][] matrix) {
        long s = 0;
        int mi = 1 << 30, cnt = 0;
        for (int[] row : matrix) {
            for (int x : row) {
                cnt += x < 0 ? 1 : 0;
                int y = Math.abs(x);
                mi = Math.min(mi, y);
                s += y;
            }
        }
        return cnt % 2 == 0 ? s : s - mi * 2;
    }
}