POJ 1050 To the Max

DP強化週間。
二次元配列が渡され、和が最大となるような部分長方形を求め、その和を出力する問題。

普通にDPするとO(N^4)になるのでだめ。
配列のj行目から一行ずつtmpに足していき、一行足すたびにtmpの部分配列の最大和を求めて、それらのなかでの最大値を計算している。O(N^3)。
DPなのは一次配列の最大となるサブ配列和を求める時くらい。

解けずにこのソースをほぼ写経して出してしまった。
http://www.cnblogs.com/liushang0419/archive/2011/05/02/2034607.html