最長連續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)。