给定一个由整数组成二维矩阵（r*c），现在需要找出它的一个子矩阵，使得这个子矩阵内的所有元素之和最大，并把这个子矩阵称为最大子矩阵。 例子： 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 其最大子矩阵为：
9 2 -4 1 -1 8 其元素总和为15。
输入 第一行输入一个整数n（0<n<=100）,表示有n组测试数据； 每组测试数据： 第一行有两个的整数r，c（0<r,c<=100），r、c分别代表矩阵的行和列； 随后有r行，每行有c个整数； 输出 输出矩阵的最大子矩阵的元素之和。 样例输入 1 4 4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 样例输出 15 思路：刚开始我想的方法要用到3个for循环感觉会超时，然后就去看网上的思路，发现和我想得一样，也是醉了。 这个和NYOJ-983-首尾相连的数组的最大数组和一样，都是NYOJ-44字串和的变形，不过这个要难一些，我们可以把 数组压缩成字符串来求，其中还用到了尺取法，然后求出每一串的最大值就行了。#include <stdio.h>#include <string.h>#include <algorithm>int a[105][105];int main(){ using namespace std; int n; int i,j; int max_d; int sum,dp; scanf("%d",&n); while(n--) { memset(a,0,sizeof(a)); max_d = -0x3f3f3f3f; int r,c; scanf("%d%d",&r,&c); for(i=1; i<=r; i++) { for(j=1; j<=c; j++) { scanf("%d",&a[i][j]); a[i][j] += a[i-1][j]; //每一个数都等于它+上面数的和 } } for(i=1; i<=r; i++) { for(j=0; j<i; j++)//尺取法的范围 { sum = 0; for(int l=1; l<=c; l++)//把数组压缩成串（化面成线） { dp = a[i][l] - a[j][l]; sum += dp; max_d = max(sum , max_d); if(sum < 0) { sum = 0; } } } } printf("%d\n",max_d); } return 0;}
