开始元素大于结束元素的最长连续序列

Question

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

显而易见的是(O^(n^2))，但有没有更好的?

Answer 1

可以在线性时间内完成。首先让我们从二次元开始:

1. 从索引i的第一个位置开始
2. 将索引j放在索引i+1的位置
3. 只要未到达数组末尾且元素a[j]/2 <= a[i]，则递增j
4. 记录索引i的"得分"。
5. 增加索引i并返回步骤2。
6. 当所有指标都被覆盖时，取得分最高的指标。

问题是要意识到，如果您在步骤3中失败了一对(i, j)，那么它意味着:

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

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

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