有一种O(N*logC)算法，其中算法C与数组的最大元素值成比例。与最近的一些较复杂的算法相比，该算法更易于理解，并且可以在短时间内实现，并且在实践中仍然足够快。

为简单起见，我们假设数组中至少有一个非负整数。

该算法基于二进制搜索。首先，我们可以发现最终答案必须在range内[0, max(A)]，并且在每次迭代中将此间隔减半，直到足够小（例如10
-6）。在每次迭代中，假设可用间隔为[a,b]，我们需要检查最大平均值是否不小于(a+b)/2。如果是这样，我们得到一个较小的间隔[(a+b)/2, b]，否则我们得到[a, (a+b)/2]。

现在的问题是：给定一个数字K，如何检查最终答案至少是K？

假设平均至少K，存在着一些i，j这样(A[i] + A[i+1] + ... + A[j]) / (j - i + 1) >= K。我们将两边都乘以(j-i+1)，然后将右侧向左移动，我们得到(A[i] - K) + (A[i+1] - K) + ... + (A[j] - K) >= 0。

因此，让B[i] = A[i] - K我们只需要找到一个这样的时间间隔[i, j]（j - i + 1 > L）B[i] + ... + B[j] >= 0。现在的问题是：给定数组B和长度L，我们要找到一个最大和的间隔，其长度大于L。如果最大和为>= 0，K则可以使用原始平均值。

第二个问题可以通过线性扫描解决。让sumB[0] = 0，sumB[i] = B[1] + B[2] + ... + B[i]。对于每个索引i，以结尾的最大总和间隔B[i]为sumB[i] - min(sumB[0], sumB[1], ..., sumB[i-L-1])。当以递增的方式扫描阵列时i，我们可以保持min(sumB[0], ..., sumB[i-L-1])实时运行。

子问题的时间复杂度为O(N)。而且我们需要O(logC)迭代，因此总复杂度为O(N*logC)。

Ps这种“平均问题”属于一类称为分数规划的问题。类似的问题是最小平均加权生成树，最小平均加权循环等。

再次PS。这O(logC)是一个宽松的界限。我认为我们可以通过一些仔细的分析来减少它。