51Node 1051---最大子矩阵和

题目链接

一个M*N的矩阵，找到此矩阵的一个子矩阵，并且这个子矩阵的元素的和是最大的，输出这个最大的值。

例如：3*3的矩阵：

-1 3 -1

2 -1 3

-3 1 2

和最大的子矩阵是：

3 -1

-1 3

1 2

Input

第1行：M和N，中间用空格隔开（2 <= M,N <= 500)。

第2 - N + 1行：矩阵中的元素，每行M个数，中间用空格隔开。(-10^9 <= M[i] <= 10^9)

Output

输出和的最大值。如果所有数都是负数，就输出0。

Input示例

Output示例

7

思路：矩阵N行M列，枚举列 两层循环求出i到j列的和，那么得到N个数的序列，求出这个序列的最大子段和即为最大子矩阵的和；

代码如下：

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

using namespace std;

long long a[][];

int main()

{

    ///cout << "Hello world!" << endl;

    int M,N;

    while(scanf("%d%d",&N,&M)!=EOF)

    {

        for(int i=;i<=M;i++)

        {

            a[i][]=;

            for(int j=;j<=N;j++)

            {

                long long x;

                scanf("%lld",&x);

                a[i][j]=a[i][j-]+x;

            }

        }

        long long sum,tmp=;

        for(int i=;i<=N;i++)

        {

            for(int j=i;j<=N;j++)

            {

                sum=;

                for(int k=;k<=M;k++)

                {

                    long long t=a[k][j]-a[k][i-];

                    sum+=t;

                    if(sum<) sum=;

                    if(sum>tmp) tmp=sum;

                }

            }

        }

        printf("%lld\n",tmp);

    }

    return ;

}

巴特西

51Node 1051---最大子矩阵和

最新文章

热门文章