arrays - 开始元素大于结束元素 div 2 的最长递增连续序列

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. 记录 index 的“分数” i。
5. 增加索引 i 并返回步骤 2。
6. 当覆盖所有索引时，取得分最高的索引。

关键是要意识到，如果您在第 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)。