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