(最大和问题).txt

求一个矩阵的最大和

最大和问题(1-7班)
成绩: 30

给定一个二维的有由正数和复数组成的整数矩阵，找出其中具有最大和的子矩阵。一个矩阵的和就是该矩阵中所有元素的和。本题中，具有最大和的子矩阵成为最大子矩阵。子矩阵是指位于整个矩阵中任何一个1x1或更大的连续的子矩阵。例如，在矩阵

  0 -2 -7  0
  9  2 -6  2
 -4  1 -4  1
 -1  8 -0 -2中，其最大子矩阵在其左下角：

  9  2
 -4  1
 -1  8输入
输入由一个N*N的整数矩阵组成。输入的第一行是一个正整数N，表示该二维矩(方)阵的大小。接下来是N2个整数，用空格(多个空格或换行)隔开。这N2个整数以行为主顺序构成矩阵(如所有整数从左到右先构成第一行，接着余下所有整数再从左到右构成第二行，以此类推)。N最大可取100。矩阵元素的取值范围是[-127, 127]。

输出
最大子矩阵的和。

提示
此题目要仔细考虑如何降低循环的次数，否则当输入很大时需要很长时间才能得到结果。




测试输入 4  0 -2 -7  0
  9  2
 -6  2
 -4  1 -4  1 -1  8 -0 -2
 
期待的输出 15