最大子矩阵
题目描述
有一个包含正数和负数的二维矩阵。矩阵的和是指矩阵中所有元素的和。现在给定一个这样的矩阵,求出一个子矩阵使得子矩阵的和最大,并输出最大值。例如矩阵:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
和最大的子矩阵为:
9 2
-4 1
-1 8
和为 15 是该矩阵中和最大的子矩阵
输入描述
输入第一行为一个 NN 表示矩阵的行数和列数。接下来有 NN 行,每行 NN 个数,代表矩阵的元素. 1 \leq N \leq 801≤N≤80 , 并且每一个元素都在 [−127,127] 的区间中
输出描述
最大子矩阵的和
样例输入
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
样例输出
15
要多组输入输出
https://blog.csdn.net/Richr_Wong/article/details/40622667?locationNum=6&fps=1
#include<stdio.h>
#define N 102
int map[N][N]={0};
int getMax(int (*a)[N],int n,int (*b)[N])
{
int i,sum=a[0][1]-b[0][1],t=0;
for(i=1;i<=n;i++)
{
if(t>0)
{
t+=(*a)[i]-(*b)[i];
}
else
{
t=(*a)[i]-(*b)[i];
}
sum=t>sum?t:sum;
}
return sum;
}
int main()
{
int m,n,p,i,j,k,max;
scanf("%d%d",&m,&n);
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&map[i][j]);
map[i][j]+=map[i-1][j];
}
}
max = map[1][1];
for(i=1;i<=m;i++)
{
for(j=i;j<=m;j++)
{
k=getMax((int (*)[102])map[j],n,(int (*)[102])map[i-1]);
max=max>k?max:k;
}
}
printf("%d\n",max);
return 0;
}