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

[qwerthhusn]

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

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

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

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

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

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

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

[Abmcar]

应该没了吧，而且你这考 od 又不是可信
看 op 水平，不刷这种题闭着眼考也能过吧

[chaoxu]

考虑 m=n ，则这个问题是 APSP-hard ，没人知道 O(n^{3-\epsilon})复杂度的算法。

Backurs, Arturs; Dikkala, Nishanth; Tzamos, Christos (2016), "Tight Hardness Results for Maximum Weight Rectangles", Proc. 43rd International Colloquium on Automata, Languages, and Programming: 81:1–81:13, doi:10.4230/LIPIcs.ICALP.2016.81