我有一个排序好的数组,希望高效地找到从开头到结尾最长的连续子序列,使得array[begin]>=array[end] div 2
。
显然的方法是(O^(n^2)),但是否有更好的方法?
a [j] / 2 <= a [i]
,就增加j(i,j)
,您在步骤3中失败,则意味着:for every i < k < j, a[k] <= a[i]/2
a[j] > a[i]/2
j
的k
将导致得分更小,因为a[j] > a[i]/2 > a[k]/2
。因此下一个要开始的索引是j
。O(n^2)
降至O(n)
。然后选择具有最大分数的索引显然是O(n)
。