Liste liée dans l'algorithme des sous-séquences de notation maximale

Question

Pour un projet, j'implémente le Toutes les sous-séquences de notation maximale algorithme. Dans la partie d'analyse de l'article, il décrit une optimisation qui fait fonctionner l'algorithme en temps linéaire. À savoir, lorsque vous effectuez la recherche de la valeur la plus à droite de $ j $ qui satisfait $ l_j <l_k $, nous pouvons rechercher une liste liée avec des valeurs de $ l_j $ en diminuant monotone.

Je suis légèrement confus sur la façon dont cela fonctionne. Si nous stockons un pointeur vers l'élément $ j $ que nous avons trouvé à l'étape 3, alors nous devons commencer à itération avec quelques Élément de l'étape 1. Quel élément fonctionnerait en tant que chef de la liste liée dans ce cas? En d'autres termes, à l'étape 1, au lieu de rechercher dans toute la liste, avec quel élément commençons-nous à rechercher?

j'ai trouvé Ces notes de conférences Plus facile à lire que le papier réel. J'ai également mis en œuvre une version $ o (n ^ 2) $ de l'algorithme dans go ici, que quiconque peut utiliser pour référencer. Cependant, j'aimerais une aide à réduire la complexité à $ o (n) $. Toute aide serait appréciée!