给定一个由整数组成二维矩阵(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个整数; - 输出
- 输出矩阵的最大子矩阵的元素之和。
思路:拆分为一维数组,然后根据动态规划求一段数据的最大和。AC代码:
#include<iostream>
#include<cstring>
#include<string>
#include<stdio.h>
using namespace std;
int a[110][110],f[10100],row,column,Max,sum;
int main()
{
int test;
scanf("%d",&test);
while(test--)
{
Max=-10000;
memset(f,0,sizeof(0));
memset(a,0,sizeof(0));
int i,j,k=1;
cin>>row>>column;
for(i=1;i<=row;++i)
for(j=1;j<=column;++j)
{
scanf("%d",&a[i][j]);
f[k++]=a[i][j];
}
for(i=1;i<=column;++i)
for(j=i;j<=column;++j)
if(i==j)
{
int temp=0;
for(k=0;k<row;++k)
{
temp=temp+f[k*column+j];
if(temp>Max) Max=temp;
if(temp<0) temp=0;
}
}
else if(i!=j)
{
int temp1,temp2,temp3=0;
temp1=i;temp2=j;
for(k=0;k<row;++k)
{
for(temp1=i;temp1<=temp2;++temp1) //注意变量之间的影响~~
{
temp3=temp3+f[k*column+temp1];
}
if(temp3>Max) Max=temp3;
if(temp3<0) temp3=0;
}
}
cout<<Max<<endl;
}
// system("pause");
return 0;
}