算法学习之路|最大子阵

题目大意

给定一个 n×m 的矩阵 A，求 A中的一个非空子矩阵，使这个子矩阵中的元素和最大。其中，A的子矩阵指在 A 中行和列均连续的一部分。

输入格式

输入的第一行包含两个整数 n,m(1≤n,m≤50),分别表示矩阵 A 的行数和列数。接下来 n行，每行 m 个整数，表示矩阵 Ai,j​(−1000≤Ai,j​≤1000)。

输出格式

输出一行，包含一个整数，表示 A中最大的子矩阵中的元素和。

样例输入

3 3

2 -4 1

-1 2 1

4 -2 2

样例输出

6

找出状态方程：（状态dpi代表左顶点固定为1,1;右顶点为i,j的矩阵的元素和。）

1.左顶点固定为1,1;右顶点为i,j的矩阵的元素和：

dpi+=dpi-1+dpi-dpi-1;

2.左顶点为i,j;右顶点为i-k,j-l的矩阵(即其中一种子阵)元素和：

dpi-dpi-k-dpi+dpi-k;