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

EN

它可以在线性时间内完成。首先，让我们从二次型开始：

如果未到达数组的末尾，则从第一个位置开始，在索引i+1

• As的位置增加索引i.

• increment j，元素a[j]/2 <= a[i]，j
  1. 记录索引i.
  2. increment索引i的“分数”并返回步骤2。
  3. 覆盖所有索引后，取分数最大的索引。

  <

  1. >G218

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