问题描述

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

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

输入格式

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

　　接下来n行，每行m个整数，表示矩阵A。

输出格式

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

样例输入

- -

  -

- -

样例输出

样例说明

　　取最后一列，和为10。

数据规模和约定

　　对于50%的数据，<=n, m<=；

　　对于100%的数据，<=n, m<=，A中每个元素的绝对值不超过5000。

 #include <stdio.h>

 #include <stdlib.h>

 #include <string.h>

 #define N 500

 int main(void)

 {

     int i,j,k,max,sum;

     int n,m;

     int dp[N+][N+];

     memset(dp,,sizeof(dp));

     scanf("%d%d",&n,&m);

     for (i= ; i<=n ; i++)

     {

         for (j= ; j<=m ; j++)

         {

             scanf("%d",&k);

             dp[i][j] = dp[i-][j] + k;//预处理：同一列中，前i行的和

         }

     }

     max = -0x3f3f3f3f;

     for (i= ; i<=n ; i++)//确定起始行:i

     {

         for (j=i ; j<=n ; j++)//确定终止行:j

         {

             sum = ;

             for (k= ; k<=m ; k++)//计算j-i行，最大k段和

             {

                 if (sum >= )

                     sum += dp[j][k]-dp[i-][k];    //累加k段和

                 else

                     sum = dp[j][k]-dp[i-][k];    //获得当前位置的值

                 max = max>sum?max:sum;

             }

         }

     }

     printf("%d",max);

     return ;

 }