如何快速找到最大，平均间隔时间？ [英] How to quickly find the maximum-average interval?

问题描述

这是一个整数数组 A [N] ，我想找到一个间隔 [I，J] 具有最大化的平均（A [I] + A [1 + 1] + ... + A [J]）/（的J - 我+ 1）。

From an integer array A[N], I'd like to find an interval [i,j] that has a maximized average (A[i] + A[i + 1] + .. + A[j]) / (j - i + 1).

间隔（的J - 我+ 1）的长度。应大于→ （L＆GT; = 1）

我的想法是要计算平均为每个I〜Ĵ，但速度太慢，做的是这样的。（N是太大了）

What I thought was to calculate an average for every i ~ j, but it is too slow to do like this.(N is too big)

有没有一种算法比更快的O（N ^ 2）？或者，我想知道是否存在的一个随机的方法。

Is there an algorithm faster than O(N^2)? Or I'd like to know whether there exists a randomized method for that.

推荐答案

有一个 O（N * logC）算法，其中 C 成正比的阵列的最大元素值。在最近的论文一些更复杂的算法相比，这种算法是更容易理解，并可以在很短的时间来实现，并且仍然足够快，在实际

There is an O(N*logC) algorithm, where C is proportional to the maximum element value of the array. Comparing with some more complicated algorithms in recent papers, this algorithm is easier to understand, and can be implemented in a short time, and still fast enough in practical.

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

For simplicity, We assume there is at least one non-negative integers in the array.

该算法是基于二进制搜索。首先，我们可以发现，最后的答案必须在范围 [0，最大值（A）] ，我们一半的时间在每次迭代，直到小足（10 ^-6 为例）。在每次迭代中，假设可用的时间间隔为 [A，B] ，我们需要检查是否最大平均不大于以下（A + B ）/ 2 。如果是这样，我们得到一个较小的区间 [（A + B）/ 2，B] ，否则我们得到 [A，（A + B ）/ 2] 。

The algorithm is based on binary search. At first, we can find that the final answer must be in the range [0, max(A)], and we half this interval in each iteration, until it is small enough (10^-6 for example). In each iteration, assume the available interval is [a,b], we need to check whether the maximum average is no less than (a+b)/2. If so, we get a smaller interval [(a+b)/2, b], or else we get [a, (a+b)/2].

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

Now the problem is: Given a number K, how to check that the final answer is at least K?

假设平均至少 K ，也存在一些我，Ĵ，使得（A [I] + A [1 + 1] + ... + A [J]）/（的J - 我+ 1）＆GT; = K 。的K - 我们通过（J-I + 1），然后将右侧向左，我们得到（A [1]乘双方）+（A [1 + 1] - K）+ ... +（A [J] - K）＆GT; = 0 。

Assume the average is at least K, there exist some i, j such that (A[i] + A[i+1] + ... + A[j]) / (j - i + 1) >= K. We multiply both sides by (j-i+1), and move the right side to left, and we get (A[i] - K) + (A[i+1] - K) + ... + (A[j] - K) >= 0.

所以，让 B [I] = A [1] - K ，我们只需要找到一个时间间隔 [I，J] （的J - 我+ 1→1 ），使得 B [I] + ... + B [J]。 ＆GT; = 0 。现在的问题是：由于阵 B 和长度→，我们要找到的最高金额的间隔长度为超过→。如果最大总和＆GT; = 0 ，原来的平均数量 K 可以

So, let B[i] = A[i] - K, we only need to find an interval [i, j] (j - i + 1 > L) such that B[i] + ... + B[j] >= 0. Now the problem is: Given array B and length L, we are to find an interval of maximum sum whose length is more than L. If the maximum sum is >= 0, the original average number K is possible.

的第二个问题可以通过线性扫描来解决。让 sumB [0] = 0 ， sumB [I] = B [1] + B [2] + ... + B [I] 。对于每个指数我，最大和的区间这在结束B〔I] 是 sumB [I] - 分（sumB [0]，sumB [1]，...，sumB [IL-1]）。当随着我扫描该阵列，就可以维持分（sumB [0]，...，sumB [IL-1]）的飞行。

The second problem can be solved by linear scan. Let sumB[0] = 0, sumB[i] = B[1] + B[2] + ... + B[i]. For each index i, the max-sum interval which ended at B[i] is sumB[i] - min(sumB[0], sumB[1], ..., sumB[i-L-1]). When scanning the array with increasing i, we can maintain the min(sumB[0], ..., sumB[i-L-1]) on the fly.

的子问题的时间复杂度为 O（N）。我们需要 O（logC）迭代，所以总的复杂性是 O（N * logC）。

The time complexity of the sub-problem is O(N). And we need O(logC) iterations, so the total complexity is O(N*logC).

P.S。这种类型的普通问题属于一个家庭的所谓分数规划的问题。类似的问题是最小平均加权生成树，最小平均加权周期等。

P.s. This kinds of "average problem" belongs to a family of problems called fractional programming. The similar problems are minimum average-weighted spanning tree, minimum average-weighted cycle, etc.

P.S。再次。该 O（logC）是一个松散的约束。我认为，我们可以通过一些细致的分析酌减。

P.s. again. The O(logC) is a loose bound. I think we can reduce it by some careful analysis.

这篇关于如何快速找到最大，平均间隔时间？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！