| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank Statistics |
Problem D
最大子矩阵
Time Limit: 1000ms
Memory Limit: 65536kb Description
相信大家都做过传说中“To the max”这题吧，大致描述如下：给你一个全部由数字组成的大小为N*M的矩阵，该矩阵包含了若干个子矩阵，定义子矩阵的和为该子矩阵中所有数字之和，我们可以通过比较所有子矩阵，找出最大子矩阵的和。 例如有如下一个矩阵： 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 那么最大子矩阵和为15，对应子矩阵为： 9 2 -4 1 -1 8 相信大家都能快速求解出该问题。其实想一想，还可以求出满足子矩阵和最大的子矩阵的个数(如上例中只有1个子矩阵和为15且最大)。 亲，相信难不到你们的！！！ Input
第一行输入一个数T(T<=20)，代表下面将有T组测试数据。每组测试数据包括两部分：第一部分：两个正整数N,M (0<N,M<=100)，分别矩阵的行和宽。 第二部分：一个N*M的数字矩阵，该矩阵中每个数字的范围为[-10000, 10000]。 Output
针对每组测试数据，输出最大子矩阵和、最大子矩阵的个数。用空格隔开。
Sample Input
1 2 3 0 0 0 0 0 0 Sample Output
0 18 |