一、思路
最大子矩阵和的方法和最大字段和一样
先单独对每行求最大字段和(此时,子矩阵的行为1,就是最大字段和了)
然后,把第i行后的各行对应列的元素加到第i行的对应列元素,每加一行,就求一次最大字段和,这样就把子矩阵的多行压缩为一行了,一行了就是最大字段和了
也可以这样理解:
a11 a12 a13
a21 a22 a23
a31 a32 a33
如图,先求第一行最大子段和,再求第一行跟第二行合起来的最大子段和,如a21+a11, a22+a12, a23+a13 的最大子段和,再求第一到第三合起来的最大子段和,如a11+a21+a31, a12+a22+a32, a13+a23+a33的最大子段和…..以此类推,直到求出整个矩阵的合起来的最大子段和,求出他们之中最大的那个和就是解.
二、AC code
#include <stdio.h>
#include <stdlib.h>
int m[101][101];
int main()
{
int n,max,i,j,k,tmp;
while(scanf("%d",&n) != EOF)
{
max=-10000;
/*
输入时,顺便求出各行的最大字段和的最大值
*/
for(i=0;i<n;++i)
{
tmp=0;
for(j=0;j<n;++j)
{
scanf("%d",&m[i][j]);
if(tmp>0)tmp+=m[i][j];
else tmp=m[i][j];
if(tmp>max)max=tmp;
}
}
for(i=0;i<n-1;++i)
{
for(j=i+1;j<n;++j)
{
tmp=0;
for(k=0;k<n;++k)
{
//相当于把子矩阵多行压缩为一行了
m[i][k]+=m[j][k];
if(tmp>0)tmp+=m[i][k];
else tmp=m[i][k];
if(tmp>max)max=tmp;
}
}
}
printf("%d\n",max);
}
return 0;
}
时间: 2024-11-05 04:50:49