最长连续sebsequenece其中开始元素大于结束元素div 2

Question

我有一个排序的数组，我想有效地找到最长的连续子序列开始结束，如array[begin]>=array[end] div 2。

显而易见的是（O ^（n^2）），但是有更好的吗？

Answer 1

它可以在线性时间内完成。首先让开始与二次：在具有索引i

穿戴索引j第一位置

1. 开始索引的位置i+1
2. 只要未达到该阵列的端部和元件a[j]/2 <= a[i]，增量j
3. 记录索引i的“得分”。
4. 递增索引i并返回步骤2.
5. 当涵盖所有索引时，以最大分数获取索引。

美中不足的是要认识到，如果你失败的步骤3一对(i, j)，那么就意味着：

for every i < k < j, a[k] <= a[i]/2 
a[j] > a[i]/2 

因此，在步骤5中，将任何k小于j将导致一个较小的分数，因为a[j] > a[i]/2 > a[k]/2。因此，开始的下一个索引是j。

现在我们在计算任何分数时最多访问一次索引。这将步骤从O(n^2)减少到O(n)。那么获得最高分的指数显然是O(n)。