太难了，有人问了一道刚做的算法题。。。
The following article is from 吴师兄学算法 Author 吴师兄
第一时间收到文章更新
最近在 LeetCode 的讨论区发现好多同学在求助，因为他们遇到了一些真题，不知道如何处理。
比如一道和堆相关的真题。
很多同学做了几百道 LeetCode ，第一次接触真题都会有点懵的，所以得刻意练习，特别是一些 hard 真题，比如下面这一道，非常有难度，也是前不久有学员问的题目。
题目描述
给定一个二维整数矩阵，要在这个矩阵中。选出一个子矩阵，使得这个子矩阵内所有的数字和尽量大
我们把这个子矩阵称为 “和最大子矩阵”，子矩阵的选取原则，是原矩阵中一段相互连续的矩形区域
输入描述
输入的第一行包含两个整数N,M
(1 <= N,M <= 10)
表示一个 N 行 M 列的矩阵
下面有N行 每行有M个整数
同一行中每两个数字之间有一个空格
最后一个数字后面没有空格
所有的数字得在-1000 ~ 1000之间
输出描述
输出一行，一个数字。表示选出的“和最大子矩阵”内所有数字的和
示例
输入
3 4
-3 5 -1 5
2 4 -2 4
-1 3 -1 3
输出
20
说明
一个3*4的矩阵中 后面3列的和为20，和最大
解题思路
如何表示一个子矩阵
一个子矩阵可以由四个参数决定，分别为上底、下底、左宽、右宽，分别用变量a、b、c、d表示的话，如下图中灰色区域为通过四个参数所确定的矩形。
如果我们想要枚举所有子矩阵，只需要分别枚举a、b、c、d，写一个4层嵌套的for循环即可。
for a in range(n):
for b in range(a, n):
for c in range(m):
for d in range(c, m):
pass
暴力解法
暴力解法是很容易想到的，我们只需要枚举所有的子矩阵，然后对每一个子矩阵进行矩阵内所有元素求和即可。其核心代码为
for a in range(n):
for b in range(a, n):
for c in range(m):
for d in range(c, m):
submat_sum = 0
for i in range(a, b+1):
for j in range(c, d+1):
submat_sum += mat[i][j]
ans = max(submat_sum, ans)
注意到会出现6层for循环嵌套，时间复杂度为
(1 <= n, m <= 10)，故取最大值时复杂度约为，无法通过全部用例，故应该思考如何优化。二维前缀和优化
注意，该方法和LeetCode 304、二维区域和检索 - 矩阵不可变 是类似的。
注意到每一个子矩阵的计算都可以用以下方式进行拆解。
拆解后的四个区域具有一个共同的特点：它们的上底均为上边界、左宽均为左边界。
因此需要考虑类似一维前缀和的方法，将所有的上底为上边界、左宽为左边界（即a = 0，c = 0）的子矩阵的和提前记录在二维前缀和矩阵pre_sum_mat中。
pre_sum_mat是一个大小为(n+1)*(m+1)的矩阵，pre_sum_mat[i][j]表示以第0行、第0列为开头（去得到的开区间），第i行、第j列为结尾（取不到的闭区间）的子矩阵的和。
上述的四个区域的和，就可以分别使用pre_sum_mat[b+1][d+1]，pre_sum_mat[b+1][c]，pre_sum_mat[a][d+1]，pre_sum_mat[a][c]来表示了。
这里对开/闭区间的理解是非常重要的，如果想不清楚的话，后面的代码很容易出错。如果把子矩阵用一种类似切片的方法表示（并不严谨的写法）为mat[a:b+1][c:d+1]。那么上述的分析过程可以写为
sum(mat[a:b+1][c:d+1])
= sum(mat[:b+1][:d+1]) + sum(mat[:a][:c]) - sum(mat[:b+1][:c]) - sum(mat[:a][:d+1])
= pre_sum_mat[b+1][d+1] + pre_sum_mat[a][c] - pre_sum_mat[b+1][c] - pre_sum_mat[a][d+1]
那么，在原矩阵mat中，分别以a、b、c、d为上底、下底、左宽、右宽的子矩阵的和，就可以记为
submat_sum = (pre_sum_mat[b+1][d+1] + pre_sum_mat[a][c] -
pre_sum_mat[b+1][c] - pre_sum_mat[a][d+1])
上述计算的时间复杂度为O(1)，因此这种做法规避了暴力解对子矩阵求和时出现的反复计算，降低了最内层求和时时间复杂度。如果把外部的循环体加上，代码为
for a in range(n):
for b in range(a, n):
for c in range(m):
for d in range(c, m):
submat_sum = pre_sum_mat[b+1][d+1] + pre_sum_mat[a][c] - \
pre_sum_mat[b+1][c] - pre_sum_mat[a][d+1]
ans = max(submat_sum, ans)
如果不想让最内层的索引出现+1，则可以修改for循环的范围，代码变为
for a in range(n):
for b in range(a+1, n+1):
for c in range(m):
for d in range(c+1, m+1):
submat_sum = pre_sum_mat[b][d] + pre_sum_mat[a][c] - \
pre_sum_mat[b][c] - pre_sum_mat[a][d]
ans = max(submat_sum, ans)
上述过程的时间复杂度为
。当n、m取最大值时复杂度约为，可以通过全部用例。二维前缀和矩阵的构建
二维前缀和矩阵pre_sum_mat的构建也要用到类似上述的拆分过程，其核心代码如下
pre_sum_mat = [[0] * (m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
pre_sum_mat[i][j] = pre_sum_mat[i-1][j] + pre_sum_mat[i][j-1] - \
pre_sum_mat[i-1][j-1] + mat[i-1][j-1]
要特别注意二维前缀和pre_sum_mat的大小，在两个维度上均比原矩阵矩阵mat大1。
该过程的时间复杂度为
。代码
from math import inf
n, m = map(int, input().split())
mat = list()
for _ in range(n):
row = list(map(int, input().split()))
mat.append(row)
# 构建二维前缀和数组
pre_sum_mat = [[0] * (m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
pre_sum_mat[i][j] = pre_sum_mat[i-1][j] + pre_sum_mat[i][j-1] - \
pre_sum_mat[i-1][j-1] + mat[i-1][j-1]
# 初始化答案为负无穷小
ans = -inf
# 枚举上底a
for a in range(n):
# 枚举下底b
for b in range(a, n):
# 枚举左宽c
for c in range(m):
# 枚举右宽d
for d in range(c, m):
# 此时四个参数能够表示一个子矩阵
# 根据式子计算子矩阵和，更新ans
submat_sum = pre_sum_mat[b+1][d+1] + pre_sum_mat[a][c] - \
pre_sum_mat[b+1][c] - pre_sum_mat[a][d+1]
ans = max(submat_sum, ans)
print(ans)
时空复杂度
时间复杂度：
空间复杂度：
二维前缀和矩阵所占空间。