Maximum Sum

题意翻译

给定一个含有正负数的二维数组,找出有最大和的子矩阵。矩阵的和指矩阵中所有元素的和。 一个子矩阵是任意在总矩阵中大小为1x1或更大的邻近子数组,例如在下面的矩阵中: 0 −2 −7 0 9 2 −6 2 −4 1 −4 1 −1 8 0 −2 (最大子矩阵)在左下方: 9 2 −4 1 −1 8 并且和为15. 输入: 包括一个N和NxN的矩阵 N<=100 矩阵中的数字在区间[-127,127]内 输出: 最大子矩阵的和

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=44 [PDF](https://uva.onlinejudge.org/external/1/p108.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA108/9bad502ba34d25d0111329e7b191a1e73f37eafb.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA108/396f13d4868ef41457d1488f0abfd926a952de29.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA108/68309ab00fee7fe7c208d797f30252388b43c04b.png)

输入输出样例

输入样例 #1

4
0 -2 -7 0 
9 2 -6 2
-4 1 -4 1 
-1 8 0 -2

输出样例 #1

15