蓝桥杯历届试题-最大子阵 （C++代码）

#include<cstdio>
#define maxn 520
long long n,m,sum[maxn][maxn],max;
int main(void)
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%lld",&sum[i][j]);
			sum[i][j]+=sum[i][j-1];
		}
	}
	/*printf
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			//scanf("%d",&sum[i][j]);
			//sum[i][j]+=sum[i][j-1];
			printf("%d\t",sum[i][j]);
		}
		printf("\n");
	}
	*/
	max=sum[1][1];
	for(int i=1;i<=m;i++)
	{
		for(int j=i;j<=m;j++)
		{
			long long s=0;
			for(int k=1;k<=n;k++)
			{
				
				s+=sum[k][j]-sum[k][i-1];
				if(s>max) max=s; 
				if(s<0) s=0;
			}
		}
	}
	printf("%lld",max);
	return 0;
}

解题思路:

    1.先是一个预处理，然后是进行按照贪心算法计算的，当前面的结果小于0时候，那么则舍弃前面的累加的数值，应为即使加上了，那么也只会让后面的累加的值变小，这样便找不到最大的值。

    2.注意预处理后sum[i][j]表示计算第i行前j个元素的和。



注意事项:
    1.一定要注意顺序 if(s<=0) s=0;  if(s>max) max=s;这两个语句的顺序是不能交换的，不能用一个不存的结果0和之前得到的最大值相比。