[蓝桥杯][历届试题]最大子阵

时间限制: 1Sec 内存限制: 128MB 提交: 70 解决: 14

题目描述

给定一个n*m的矩阵A，求A中的一个非空子矩阵，使这个子矩阵中的元素和最大。 

其中，A的子矩阵指在A中行和列均连续的一块。 

样例说明 
取最后一列，和为10。 
数据规模和约定 
对于100%的数据，1< =n,  m< =500，A中每个元素的绝对值不超过5000。 

输入

输入的第一行包含两个整数n,  m，分别表示矩阵A的行数和列数。 
接下来n行，每行m个整数，表示矩阵A。 

输出

输出一行，包含一个整数，表示A中最大的子矩阵中的元素和。 

样例输入

3  3 
-1  -4  3 
3  4  -1 
-5  -2  8 

样例输出

10

解题思路:

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

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



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

#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	",sum[i][j]);
        }
        printf("
");
    }
    */
    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;
}