algorithm - 最大和/面积子矩阵

Question

输入：nxn 正/负数矩阵和 k。

输出：子矩阵，其元素的最大总和除以其具有至少 k 个元素的元素数。

对于这个问题，有没有比 O(n^4) 更好的算法？

Answer 1

一种基于 FFT 的分治法来解决这个问题：

https://github.com/tearn/maximum-submatrix-sum

它不如 Kadane 的 (O(N^3) vs. O(N^3 log N)) 有效，但在解决方案构建方面确实给出了不同的看法。

Answer 2

有一个 O(n^3) 2-d kadane 算法用于在 nxn 矩阵中找到最大和子矩阵（即子矩形）。（您可以在 SO 上找到有关它的帖子，或在线阅读）。一旦您了解了算法的工作原理，很明显，如果您可以解决在 1-d 数组中找到长度至少为 m 的最大平均子区间的问题，您可以获得 O(n^3) 时间解决方案在 O(n) 时间内的 n 个数字。这确实是可能的，见论文 cs.slu.edu/~goldwasser/publications/DensityPreprint.pdf

因此，您的问题有一个 O(n^3) 时间解决方案。