给定一个n×m的矩阵A，求A中的一个非空子矩阵，使这个子矩阵中的元素和最大。其中，A的子矩阵指在A中行和列均连续的一部分。
输入格式
输入的第一行包含两个整数n,m(1≤n,m≤50)，分别表示矩阵A的行数和列数。接下来n行，每行m个整数，表示矩阵Ai,j(−1000≤Ai,j≤1000)。
输出格式
输出一行，包含一个整数，表示A中最大的子矩阵中的元素和。
样例输入
3 32 -4 1-1 2 14 -2 2
样例输出
6
/*循环每一行作为开始，b[i]为到达此行时每列的和,maxc函数求出最大连续列，类似于dp*/#include<iostream>#include<string>#include<cstring>#include<vector>#include<map>#include<set>#include<cmath>#include<algorithm>#include<queue>#include<stack>#include<cstdio>#include<functional>#define FIN freopen("input.txt","r",stdin)#define FOUT freopen("output.txt","w",stdout)using namespace std;int maxc(int b[],int n){int MAX = b[1];int t = 0;//开始为0for (int i = 1; i <= n; i++){t += b[i];if (t > MAX)MAX = t;if (t < 0)t = 0;//小于0时返回0}return MAX;}int main(){int n, m, MAX;//MAX记录最大值int s[55][55];cin >> m >> n;//行和列for (int i = 1; i <= m; i++)for (int j = 1; j <= n; j++)cin >> s[i][j];MAX = s[1][1];for (int i = 1; i <= m; i++)//循环每行作为开头{int b[55] = { 0 };for (int j = i; j <= m; j++){for (int k = 1; k <= n; k++)b[k] += s[j][k];//达到此行时每列的和MAX = max(MAX, maxc(b,n));}}cout << MAX << endl;}
