AOJ考试版's OJ 竞赛&作业 状态 竞赛&作业问题列表
登录 注册

安徽科技工程大学程序设计在线考试系统Ver3.0

诚信考试，杜绝作弊！

问题 G: 最大子矩阵

内存限制：512 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较
上一题返回比赛提交提交记录 下一题

题目描述


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

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

输入格式

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

输出格式

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

输入样例 复制 

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

输出样例 复制 

10

数据范围与提示

数据规模和约定 
对于50%的数据，1< =n,  m< =50； 
对于100%的数据，1< =n,  m< =500，A中每个元素的绝对值不超过5000。