最长上升连续子序列的起始元素大于结束元素除以2

Question

我有一个排序好的数组，希望高效地找到从开头到结尾最长的连续子序列，使得array[begin]>=array[end] div 2。

显然的方法是（O^(n^2)），但是否有更好的方法？

- user2361502

Answer 1

可以在线性时间内完成。首先从二次方开始：

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

关键是要意识到，如果对于一对(i，j)，您在步骤3中失败，则意味着：

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)。

- UmNyobe

---

在第三步，您的意思是 a[j] / 2 <=a[i] 吗？ - user2361502