J16 实践-5 最大子矩阵

题目描述

一个数字矩阵，每个格子有一个整数。请你编程求出一个子矩阵，要求他各个格子的数值和最大。 子矩阵最少必须有一格。 例如：以下是一个 $4 *4$ 的矩阵

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

其中的最大子矩阵是

 9 2
-4 1
-1 8

所以子矩阵的和为 $15$ 。

输入格式

一个整数 $n$ ，表示这是一个 $n*n$ 的矩阵。 接下来的 $n$ 行，每行 $n$ 个整数 $x$ 。

输出格式

一个整数，表示最大子矩阵的和。

样例输入

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

样例输出

15

样例分析

如上所述。

数据范围

$100\%$ 的数据：$1 \le n,x \le 100$ 。