问题 3213 --二维最大子矩阵问题

3213: 二维最大子矩阵问题

题目描述

  事实上,宇宙中可以看到的物质只占宇宙总质量的不到10%,剩下的90%多是看不见摸不着的暗物质。暗物质能量惊人,是星际航行中无穷无尽强大动力的来源,而魔法世界的魔法实际上也是利用了围绕在我们四周但我们却毫无察觉的暗物质能量。

现在,为了阻击修罗王的机器人军团,魔法世界使用了暗物质能量炮,暗物质能量炮攻击范围是一个矩形,攻击后可以使该范围内的机器人全部失灵。已知机器人军团在一个n * m二维的矩阵中,矩阵中的各元素数代表该处的机器人数量,请确定一个小的矩阵,使这个小矩阵中所有元素的和最大。

输入

第一行为两整数n,m,(1≤n,m≤200)

以下n行,每行m列,为矩阵中各元素的值。

输出

一个整数,即最大子矩阵和。

样例输入输出

输入#1 复制
4 3
1 -8 -8
1 1 1
-8 1 2
-8 1 1
输出#1 复制
7

提示

序号 标题 作者 发表时间 费用 订购数 操作