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
中。
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
。
该过程的时间复杂度为
。
代码
解法一：二维前缀和
Python
# 题目练习网址：https://www.algomooc.com/problem/P4204
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)
Java
import java.util.Scanner;
publicclassMain{ publicstaticvoidmain(String[] args){ Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int[][] mat = newint[n][m];
for (int i = 0; i for (int j = 0; j mat[i][j] = scanner.nextInt(); } }
int[][] preSumMat = newint[n + 1][m + 1];
for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { preSumMat[i][j] = preSumMat[i - 1][j] + preSumMat[i][j - 1] - preSumMat[i - 1][j - 1] + mat[i - 1][j - 1]; } }
int ans = Integer.MIN_VALUE;
for (int a = 0; a for (int b = a; b for (int c = 0; c for (int d = c; d int submatSum = preSumMat[b + 1][d + 1] + preSumMat[a][c] - preSumMat[b + 1][c] - preSumMat[a][d + 1]; ans = Math.max(submatSum, ans); } } } }
System.out.println(ans); } }
C++
#include #include #include
usingnamespacestd;
intmain(){ int n, m; cin >> n >> m; vector<vector<int>> mat(n, vector<int>(m));
for (int i = 0; i for (int j = 0; j cin >> mat[i][j]; } }
for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { 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]; } }
int ans = numeric_limits<int>::min();
for (int a = 0; a for (int b = a; b for (int c = 0; c for (int d = c; d int 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); } } } }
coutreturn0; }
C
#include #include // 用于定义负无穷
intmain(){ int n, m; scanf("%d %d", &n, &m);
int mat[n][m]; // 读取矩阵数据 for (int i = 0; i for (int j = 0; j scanf("%d", &mat[i][j]); } }
// 构建二维前缀和数组 int pre_sum_mat[n+1][m+1]; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { pre_sum_mat[i][j] = 0; } }
for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { 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]; } }
// 初始化答案为负无穷小 int ans = INT_MIN;
// 枚举上底a for (int a = 0; a // 枚举下底b for (int b = a; b // 枚举左宽c for (int c = 0; c // 枚举右宽d for (int d = c; d // 计算子矩阵的和 int 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]; // 更新答案 if (submat_sum > ans) { ans = submat_sum; } } } } }
let input = []; rl.on('line', line => { input.push(line); }).on('close', () => { let [n, m] = input[0].split(' ').map(Number); let mat = []; for (let i = 1; i <= n; i++) { mat.push(input[i].split(' ').map(Number)); }
// 构建二维前缀和数组 let pre_sum_mat = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));
for (let i = 1; i <= n; i++) { for (let j = 1; j <= m; j++) { 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]; } }
let ans = -Infinity;
// 枚举所有子矩阵 for (let a = 0; a for (let b = a; b for (let c = 0; c for (let d = c; d let 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 = Math.max(submat_sum, ans); } } } }
console.log(ans); });
Go
package main
import ( "fmt" "math" )
funcmain() { var n, m int fmt.Scanf("%d %d", &n, &m)
// 读取矩阵数据 mat := make([][]int, n) for i := 0; i mat[i] = make([]int, m) for j := 0; j fmt.Scanf("%d", &mat[i][j]) } }
// 构建二维前缀和数组 preSumMat := make([][]int, n+1) for i := 0; i <= n; i++ { preSumMat[i] = make([]int, m+1) }
for i := 1; i <= n; i++ { for j := 1; j <= m; j++ { preSumMat[i][j] = preSumMat[i-1][j] + preSumMat[i][j-1] - preSumMat[i-1][j-1] + mat[i-1][j-1] } }
// 初始化答案为负无穷 ans := math.MinInt
// 枚举所有子矩阵 for a := 0; a for b := a; b for c := 0; c for d := c; d submatSum := preSumMat[b+1][d+1] + preSumMat[a][c] - preSumMat[b+1][c] - preSumMat[a][d+1] if submatSum > ans { ans = submatSum } } } } }
