求 M 行 N 列矩阵，最大子矩阵和，有比 O(M×N)时间复杂度更低的算法吗？

能不能达到更低的时间复杂度？

实在想不出来了，感觉自己智商着实有点低啊。

马上菊花外包机考，之前从没刷过题，这几天在临阵抱佛脚，遇到个最大子矩阵问题，由于涉及到动态规划：

先看了看 0-1 背包问题，脑子烧了老半天，算是理解个大概了，但是还没有看各种变种背包问题，以及朴素 DP 解法的进一步优化。

然后去看了最大子数组和，暴力 O(N)，暴力暂存结果 O(N)，分治法 O(N×LOGN)都很好理解，最后一个 DP ，我本来想自己想一想看看能不能找到状态迁移方程，愣是没想到，然后看答案，还稍微费劲理解了一番终于算是明白了。

现在扩充到二维数组，压缩到一维数组然后 DP 达到 O(M×N)这个也没想到，最后看了答案还琢磨了很久算是搞明白了（其实本来算是比较好懂的，主要是我脑子一直在想找个状态迁移方程被绕进去，搞短路了），当 m<n 时也可以用行作为循环轴 O(N×M)这个很好理解。目前网上的很多解都是这个版本的。但是昨天我好像刷到了 O(M×N)的解，但是找不到那个链接了。

我自己想了半天也没能想出来什么好的状态迁移方程。