描述
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。
比如，如下4 * 4的矩阵
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
的最大子矩阵是
9 2
-4 1
-1 8
这个子矩阵的大小是15。输入输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N2个整数，整数之间由空白字符分隔（空格或者空行）。已知矩阵中整数的范围都在[-127, 127]。输出输出最大子矩阵的大小。
样例输入
4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2
样例输出
15
二维前缀和：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include<iostream> #include<cstring> using namespace std; int original[101][101]; int sum[101][101]; int n; void init() { cin>>n; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { cin>>original[i][j];//original init } } for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+original[i][j];//prefix_sum init } } } inline int calculate(int l_i,int l_j,int r_i,int r_j) { return sum[r_i][r_j] - sum[r_i][l_j - 1] - sum[l_i - 1][r_j] + sum[l_i - 1][l_j - 1]; } int main() { ios::sync_with_stdio(false); init(); int max_n; memset(&max_n,0x81,sizeof(max_n)); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int k=i+1;k<=n;k++){ for(int m=j+1;m<=n;m++){ int t=calculate(i,j,k,m); if(t>max_n){ max_n=t; } } } } } cout<<max_n; } |
2021.07.17重写：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cstring> #include <vector> #include <cctype> #include <set> #include <unordered_set> #include <unordered_map> #include <vector> #include <cmath> using namespace std; int n; int arr[105][105]; int pre[105][105]; inline int cal(int x1, int y1, int x2, int y2) { return pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> arr[i][j]; for (int i = 1; i <= n; i++) { //二维前缀和 for (int j = 1; j <= n; j++) { pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i-1][j-1] + arr[i][j]; } } int vMax = 0x80000000; for (int x1 = 1; x1 <= n; x1++) { for (int y1 = 1; y1 <= n; y1++) { for (int x2 = x1; x2 <= n; x2++) { for (int y2 = y1; y2 <= n; y2++) { vMax = max(vMax, cal(x1, y1, x2, y2)); } } } } cout << vMax; } |