最大和
时间限制：1000 ms | 内存限制：65535 KB
难度：5
- 描述
-
给定一个由整数组成二维矩阵（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
二维最大连续和，转化成一维的最大连续和。
01.#include
<iostream>02.#include
<string.h>03.using namespace std;04.#define
maxN 10205.int num[maxN][maxN];06.int main()07.{08.int t;09.cin>>t;10.while(t--)11.{12.int r,c;13.cin>>r>>c;14.for(int i=1;i<=r;i++)15.for(int j=1;j<=c;j++)16.{17.cin>>num[i][j]; 18.num[i][j]+=num[i-1][j];19.}20.int max_sum=num[1][1],sum=0;21.for(int i=0;i<r;i++)22.for(int j=i+1;j<=r;j++)23.{24.sum=0;25.for(int k=1;k<=c;k++)26.{27.if(sum>0)28.sum+=num[j][k]-num[i][k];29.else30.sum=num[j][k]-num[i][k];31.if(sum>max_sum)32.max_sum=sum;33.}34.}35.cout<<max_sum<<endl;36.}37.return 0;38.}