输入:正数/负数和 k 的 nxn 矩阵。
输出:子矩阵,其元素的最大总和除以至少有 k 个元素的元素数。
对于这个问题,有没有比 O(n^4) 更好的算法?
最佳答案
解决此问题的基于 FFT 的分而治之方法:
https://github.com/thearn/maximum-submatrix-sum
它不如 Kadane 的效率高(O(N^3) vs. O(N^3 log N)),但在解决方案构建方面确实给出了不同的看法。
关于algorithm - 最大总和/面积子矩阵,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13093263/