是否存在求解最大均值子矩形的O(n*m)时间复杂度算法？

首先给出结论：目前不存在已知的O(nm)时间复杂度解法，以下是具体分析：

问题本质 #

你研究的是最大均值子矩形问题，核心是在包含正负元素的矩阵中，寻找面积不超过原矩阵的子矩形，使其元素均值（和/面积）最大。这个问题是一维「最大均值子数组」的二维扩展，二者的核心难点在于均值最大化无法通过常规贪心或单次线性扫描完全解决。

现有解法的复杂度分析 #

你当前实现的O(nm²)解法（若行数n小于列数m，可优化为O(n²m)）是这类问题的经典思路：

• 枚举左右列（或上下行），将二维矩阵压缩为一维的「列和数组」
• 对压缩后的一维数组求解最大均值子数组，再更新全局最大值

这种思路的时间复杂度由枚举的维度决定，是工程上常用的可行解法，但无法达到O(nm)的线性复杂度。

为何不存在O(nm)解法？ #

目前学术界和工业界的研究表明，二维最大均值子矩形问题的最优已知时间复杂度为O(nm log C)（C为矩阵元素的最大绝对值范围），基于「二分均值+前缀和+Kadane算法」的思路：

1. 二分枚举候选均值μ
2. 将矩阵每个元素减去μ，转化为寻找是否存在子矩形的和≥0（等价于该子矩形均值≥μ）
3. 利用前缀和与Kadane算法判断是否存在符合条件的子矩形

由于二分过程需要O(log C)次迭代，每次迭代时间复杂度为O(nm)，因此总复杂度为O(nm log C)。这是目前已知的最优结果，尚未有研究能将其优化到纯O(nm)线性复杂度——核心原因是二维空间中子矩形的组合约束，无法通过单次线性扫描覆盖所有可能的最优情况。

对现有代码的小提示 #

你的一维find_max_subarray函数存在逻辑缺陷：判断是否扩展子数组的条件**(max_ending_here + arr[i])/(i - s + 1) >= arr[i]**并不等价于均值最大化的正确判断。正确的一维最大均值子数组求解应使用「二分+前缀和+单调队列」或更严谨的贪心策略，否则可能在部分测试用例中得到错误结果。

内容的提问来源于stack exchange，提问作者Itay Etelis