已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是$1\times 1$)子矩阵。
比如，如下$4\times 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\times N$的矩阵。输入的第一行给出$N\left ( 0< N\leqslant 100\right )$。再后面的若干行中，依次（首先从左到右给出第一行的$N$个整数，再从左到右给出第二行的$N$个整数……）给出矩阵中的$N^{2}$个整数，整数之间由空白字符分隔（空格或者空行）。已知矩阵中整数的范围都在$\left [ -127,127\right ]$。
输出最大子矩阵的大小。
输入
4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2
输出
15
$Pre$数组表示矩阵前缀和，即$Pre_{i,j}=\sum_{1\leqslant k\leqslant i}a_{k,j}$
$Dp_{k}$表示起始行为$i$，终止行为$j$的子矩阵在第$k$列的元素之和
#include <bits/stdc++.h> #define Enter puts("") #define Space putchar(‘ ‘) using namespace std; typedef long long ll; typedef double Db; typedef unsigned long long Ull; inline ll Read() { ll Ans = 0; char Ch = getchar() , Las = ‘ ‘; while(!isdigit(Ch)) { Las = Ch; Ch = getchar(); } while(isdigit(Ch)) { Ans = (Ans << 3) + (Ans << 1) + Ch - ‘0‘; Ch = getchar(); } if(Las == ‘-‘) Ans = -Ans; return Ans; } inline void Write(ll x) { if(x < 0) { x = -x; putchar(‘-‘); } if(x >= 10) Write(x / 10); putchar(x % 10 + ‘0‘); } int a[1001][1001]; int Dp[1001]; int Pre[1001][1001]; int Ans = -9999999; int main() { int n; n = Read(); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { a[i][j] = Read(); Pre[i][j] = Pre[i - 1][j] + a[i][j]; } for(int i = 1; i <= n; i++) for(int j = i + 1; j <= n; j++) { for(int k = 1; k <= n; k++) Dp[k] = Pre[j][k] - Pre[i - 1][k]; for(int k = 1; k <= n; k++) { Dp[k] = max(Dp[k - 1] + Dp[k] , Dp[k]); Ans = max(Ans , Dp[k]); } } Write(Ans); return 0; }
原文：https://www.cnblogs.com/Tenderfoot/p/14698550.html