求 M 行 N 列矩阵，最大子矩阵和，有比 O(M×N²)时间复杂度更低的算法吗？
qwerthhusn · 2023-07-29 12:08:48 +08:00 · 797 次点击这是一个创建于 481 天前的主题，其中的信息可能已经有所发展或是发生改变。
能不能达到更低的时间复杂度？
实在想不出来了，感觉自己智商着实有点低啊。
马上菊花外包机考，之前从没刷过题，这几天在临阵抱佛脚，遇到个最大子矩阵问题，由于涉及到动态规划：
先看了看 0-1 背包问题，脑子烧了老半天，算是理解个大概了，但是还没有看各种变种背包问题，以及朴素 DP 解法的进一步优化。
然后就去看了最大子数组和，暴力 O(N³)，暴力暂存结果 O(N²)，分治法 O(N×LOG₂N)都很好理解，最后一个 DP ，我本来想自己想一想看看能不能找到状态迁移方程，愣是没想到，然后看答案，还稍微费劲理解了一番终于算是明白了。
现在扩充到二维数组，压缩到一维数组然后 DP 达到 O(M×N²)这个也没想到，最后看了答案还琢磨了很久算是搞明白了（其实本来算是比较好懂的，主要是我脑子一直在想找个状态迁移方程被绕进去，搞短路了），当 m<n 时也可以用行作为循环轴 O(N×M²)这个很好理解。目前网上的很多解都是这个版本的。但是昨天我好像刷到了 O(M×N)的解，但是找不到那个链接了。
我自己想了半天也没能想出来什么好的状态迁移方程。
 |
1
Abmcar 2023-07-29 14:10:28 +08:00
应该没了吧，而且你这考 od 又不是可信
看 op 水平，不刷这种题闭着眼考也能过吧 |
 |
2
chaoxu 2023-11-22 00:04:49 +08:00
考虑 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 |
Select Language