La plus longue sebsequenece contiguë croissante où l'élément de début est plus grand que l'élément de fin div 2

Question

J'ai un tableau trié, et je veux trouver efficacement la plus longue sous-séquence contiguë du début à la fin de manière à ce que array[begin]>=array[end] div 2 .

La solution évidente est (O^(n^2) ), mais existe-t-il quelque chose de mieux ?

Answer 1

Cela peut être fait en temps linéaire. Commençons par le quadratique :

1. Commencez à la première position avec l'index i
2. Indice de mise en place j à la position de l'indice i+1
3. Tant que la fin du tableau n'est pas atteinte et que l'élément a[j]/2 <= a[i] , l'incrément j
4. enregistrer le "score" de l'indice i .
5. incrémenter l'indice i et revenir à l'étape 2.
6. Lorsque tous les index sont couverts, prenez l'index avec le score maximum.

Le piège est de réaliser que si vous échouez à l'étape 3 pour une paire (i, j) alors cela signifie :

for every i < k < j, a[k] <= a[i]/2
a[j] > a[i]/2

Ainsi, à l'étape 5, en passant à n'importe quel k plus petit que j conduira à un score plus faible, car a[j] > a[i]/2 > a[k]/2 . Ainsi, l'indice suivant pour commencer est j .

A présent, nous visitons un index au maximum une fois lors du calcul d'un score. Ce qui réduit cette étape de O(n^2) à O(n) . Ensuite, le choix de l'indice avec le score maximum est évidemment O(n) .