算法學習之路|最大子陣

題目大意

給定一個 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;