最大方阵和 图解题解

这道题到底在问什么

输入

matrix=[[1,-1],[-1,1]]

输出

4

输入

matrix=[[1,2,3],[-1,-2,-3],[1,2,3]]

输出

16

最优解：一步一步想明白

1. 3记牢这句话:符号翻转能把任意两个格子一起翻。没有 0 时,真正被卡死的只有负数个数的奇偶,偶数能全清成正、奇数得留一个负号;有 0 时多出的负号可被 0 吸收,相当于最小绝对值是 0。下面一遍扫描,把绝对值之和、负数个数、最小绝对值三样东西同时数出来。
2. 4扫描前先看清这个 3 乘 3 的方阵。标红的三个格子是负数,分别是 (0,1) 的 -3,(1,0) 的 -4,(2,1) 的 -7,一共三个负数。其余都是正数。我们要做的是一遍扫描,把每个格子的绝对值加起来,同时数清负数有几个、绝对值最小的是多少。
3. 5读取中扫到第 1 个格子 (0,0),它的值是 2,是个正数,绝对值是 2。先把它举起来看清楚,下一拍再把它算进三个累计量里。
4. 6已扫 1 格把绝对值 2 加进总和,和从 0 变成 2。它是正数,负数个数还是 0。它的绝对值 2 比之前更小,最小绝对值刷新成 2。这一格结算完毕,给它上色收进已扫的行列。
5. 7读取中扫到第 2 个格子 (0,1),它的值是 -3,是个负数,绝对值是 3。先把它举起来看清楚,下一拍再把它算进三个累计量里。
6. 8已扫 2 格把绝对值 3 加进总和,和从 2 变成 5。它是负数,负数个数加到 1。最小绝对值仍是 2。这一格结算完毕,给它上色收进已扫的行列。
7. 9读取中扫到第 3 个格子 (0,2),它的值是 5,是个正数,绝对值是 5。先把它举起来看清楚,下一拍再把它算进三个累计量里。
8. 10已扫 3 格把绝对值 5 加进总和,和从 5 变成 10。它是正数,负数个数还是 1。最小绝对值仍是 2。这一格结算完毕,给它上色收进已扫的行列。
9. 11读取中扫到第 4 个格子 (1,0),它的值是 -4,是个负数,绝对值是 4。先把它举起来看清楚,下一拍再把它算进三个累计量里。
10. 12已扫 4 格把绝对值 4 加进总和,和从 10 变成 14。它是负数,负数个数加到 2。最小绝对值仍是 2。这一格结算完毕,给它上色收进已扫的行列。
11. 13读取中扫到第 5 个格子 (1,1),它的值是 1,是个正数,绝对值是 1。先把它举起来看清楚,下一拍再把它算进三个累计量里。
12. 14已扫 5 格把绝对值 1 加进总和,和从 14 变成 15。它是正数,负数个数还是 2。它的绝对值 1 比之前更小,最小绝对值刷新成 1。这一格结算完毕,给它上色收进已扫的行列。
13. 15读取中扫到第 6 个格子 (1,2),它的值是 6,是个正数,绝对值是 6。先把它举起来看清楚,下一拍再把它算进三个累计量里。
14. 16已扫 6 格把绝对值 6 加进总和,和从 15 变成 21。它是正数,负数个数还是 2。最小绝对值仍是 1。这一格结算完毕,给它上色收进已扫的行列。
15. 17读取中扫到第 7 个格子 (2,0),它的值是 8,是个正数,绝对值是 8。先把它举起来看清楚,下一拍再把它算进三个累计量里。
16. 18已扫 7 格把绝对值 8 加进总和,和从 21 变成 29。它是正数,负数个数还是 2。最小绝对值仍是 1。这一格结算完毕,给它上色收进已扫的行列。
17. 19读取中扫到第 8 个格子 (2,1),它的值是 -7,是个负数,绝对值是 7。先把它举起来看清楚,下一拍再把它算进三个累计量里。
18. 20已扫 8 格把绝对值 7 加进总和,和从 29 变成 36。它是负数,负数个数加到 3。最小绝对值仍是 1。这一格结算完毕,给它上色收进已扫的行列。
19. 21读取中扫到第 9 个格子 (2,2),它的值是 2,是个正数,绝对值是 2。先把它举起来看清楚,下一拍再把它算进三个累计量里。
20. 22已扫 9 格把绝对值 2 加进总和,和从 36 变成 38。它是正数,负数个数还是 3。最小绝对值仍是 1。这一格结算完毕,给它上色收进已扫的行列。
21. 23扫描完成九个格子全部扫完。绝对值之和是 38,负数个数是 3,绝对值最小的是 1,就在中心那个正数格 (1,1)。三个数据齐了,接下来只看一件事:负数个数是奇是偶。
22. 24奇偶裁决负数个数是 3,是个奇数。这个例子里没有 0,前面说过每次操作翻两个符号,非零格子里负号的奇偶变不了,奇数就永远是奇数。所以无论怎么折腾,最后至少要剩一个负号,清不干净。既然躲不掉,那就想办法让这一个负号带来的损失尽可能小。
23. 25牺牲最小格三个负号里,通过翻转可以把其中两个配对清成正,剩下这一个负号,我们不给别人,专门丢给绝对值最小的格子 (1,1)。注意它原本是正数 1,现在被牺牲成 -1。为什么选它,因为一个本该加 1 的格子变成减 1,一来一回损失是 2 乘 1,这个损失在所有格子里最小。
24. 26答案 = 36最终布局:八个格子都是正的,只有中心 (1,1) 留成 -1。总和等于绝对值之和 38 减去被牺牲的那 2 乘 1,也就是 38 减 2,等于 36。这就是这个方阵能达到的最大和。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问