题目描述

给定一个 $n$ 行 $m$ 列的整数矩阵（元素可能为正数或负数），请从中找出一个非空子矩阵，使得该子矩阵内所有元素的和最大，输出这个最大和。

输入格式

第一行两个整数 $n, m$。

接下来 $n$ 行，每行 $m$ 个用空格隔开的整数，表示矩阵。

输出格式

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

数据范围

$1 \le n, m \le 500$，$-1000 \le a_{i,j} \le 1000$。

样例

输入样例 1

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

输出样例 1

15

提示

例如样例中，取第 $2$ 行第 $1\sim2$ 列（$9,2$）与第 $4$ 行第 $1\sim2$ 列（$-1,8$）并不相邻；正确的最大子矩阵是第 $2$ 行与第 $4$ 行之间、第 $1\sim2$ 列的子矩阵：$9+2-4+1-1+8=15$。

做法：枚举行的上边界与下边界（$O(n^2)$），把每一列在这个行区间内的和压成一维数组，再用「最大子段和」$O(m)$ 求出这个行区间下的最优列区间。总复杂度 $O(n^2 m)$。