La plus longue sous-séquence «délimitée»

Question

Étant donné une séquence d'objets comparables $ a_1, a_2, ldots a_n, $ à quelle vitesse pouvons-nous trouver la sous-séquence la plus longue $ s $ telle que $ s_i> s_1 $ pour $ i> 1 $? Ou de manière équivalente, à quelle vitesse pouvons-nous trouver

$$ Undernset {i} { arg max} ; # {j mid a_j> a_i, i <j le n } $$

Peut-il être fait dans moins de $ Omega (n , lg n) $ comparaisons dans le pire des cas?

Un algorithme $ theta (n , lg n) est de scanner de droite à gauche, en insérant chaque élément dans un arbre équilibré, en gardant une trace du nombre d'éléments de l'arbre.

Cela a été inspiré par ce fil sur reddit.