传送门：https://www.51nod.com/Challenge/Problem.html#!#problemId=1051
一个M*N的矩阵，找到此矩阵的一个子矩阵，并且这个子矩阵的元素的和是最大的，输出这个最大的值。
例如：3*3的矩阵：
-1 3 -1
2 -1 3
-3 1 2
和最大的子矩阵是：
3 -1
-1 3
1 2
收起
输入
第1行：M和N，中间用空格隔开（2 <= M,N <= 500)。 第2 - N + 1行：矩阵中的元素，每行M个数，中间用空格隔开。(-10^9 <= M[i] <= 10^9)
输出
输出和的最大值。如果所有数都是负数，就输出0。
输入样例
3 3 -1 3 -1 2 -1 3 -3 1 2
输出样例
7
题意很明了，做法就是n^2枚举l到r区间，然后对于l到r区间每一行的和可以通过前缀和O1得到，接着就是1到n行在l到r列中求一个最大连续字段和的问题了，dp即可
#include <bits/stdc++.h>
#include <time.h>
#define first fi
#define second seusing namespace std;typedef long long ll;
typedef double db;
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
const double eps = 1e-9;
typedef pair<int,int> P;
const int maxn = 600;
const ll mod = 1e9 + 7;
inline int sign(db a) { return a < -eps ? -1 : a > eps;}
ll mul(ll a,ll b,ll c) { ll res = 1; while(b) { if(b & 1) res *= a,res %= c; a *= a,a %= c,b >>= 1; } return res;}
ll phi(ll x) { ll res = x; for(ll i = 2; i * i <= x; i++) { if(x % i == 0) res = x / i * (i - 1); while(x % i == 0) x /= i; } if(x > 1) res = res / x * (x - 1); return res;}
ll c,n,k,m;
ll a[maxn][maxn];
ll s[maxn][maxn];
int main() {ios::sync_with_stdio(false);while(cin >> m >> n){for(int i = 1;i <= n;i++)for(int j = 1;j <= m;j++)cin >> a[i][j];for(int i = 1;i <= n;i++)for(int j = 1;j <= m;j++)s[i][j] = s[i][j - 1] + a[i][j];ll ans = 0;for(int i = 1;i <= m;i++){for(int j = i;j <= m;j++){ll sum = 0,Max = 0;for(int k = 1;k <= n;k++){ll cha = s[k][j] - s[k][i - 1];sum += cha;if(sum < 0){sum = 0;continue;}Max = max(Max,sum);}ans = max(Max,ans);}}cout << ans << endl;}//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}