求教，有道难题

hdm2968

这是一道竞赛题，主要是因为时间比较短，所以用穷举的方法不能通过。以下是我的转述：
在一个NxN矩阵中，它的元素是整数（包括正负），矩阵内有多个子矩阵，求这些子矩阵中的元素的和的最大者。子矩阵的形状大小最小为1x1，最大为NxN。
例如：
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
这个矩阵中，加起来的和最大的子矩阵是左下角的：
9 2
-4 1
-1 8
因此，输出和 15

输入一个整数N（最大为100），接着输入N*N个整数作为矩阵NxN的元素（元素在[-127,128]内）。
输出一个整数，代表加起来的和最大的子矩阵的和。
（无需输出子矩阵）

这题我不明白怎样不用穷举法去做，谢谢赐教 [em1]

hdm2968

已解决，DP,O(n^3)，但不知道分治怎样做

gogoplayer

动态规划有点意思
你的状态转移方程怎么写

飞翔的梦想

有个设想

设置A为0   也为最后结果

然后矩形所有数相加   得到答案  赋予A

然后  将矩形4条最外边的的数分别相加  即  矩形最左边列 最右边列  最上面列  最下面列

加后得到最小的一列  将这列去掉   然后将剩余各个数相加

得到结果  将这结果与A相比   如果大于A  那么  将最新值赋予A  如果小于  A值不动

然后将去掉最小值边的矩形又做各个外边数相加求和

然后去掉最小边        求剩余数和   与A比较

最后   当剩一个非矩形时   整个程序结束   将A值输出  

（如果要指出最大的矩形数列的话   可以引入新数列做表识  呵呵  可能麻烦  也许有更好办法）

飞翔的梦想

对了

如果出现几条边相加结果一样的情况

还不知道什么办法最好

一种是每个边的元素3次方后比较  不过结果是否准确 未证实

如果结果也一样又如何  这些还需要思考

呵呵    可以按照这一计算原来来计算  不知道楼主觉得如何