Elenco collegato nell'algoritmo di successioni di punteggio massimo

Question

Per un progetto, sto implementando il Tutte le successioni di punteggio massimo algoritmo. Nella parte dell'analisi del documento, descrive un'ottimizzazione che fa funzionare l'algoritmo in tempo lineare. Vale a dire, quando effettua la ricerca del valore più a destra di $ j $ che soddisfa $ l_j <l_k $, possiamo cercare un elenco collegato con valori monotonicamente che diminuiscono $ l_j $.

Sono leggermente confuso su come funziona. Se archiviamo un puntatore all'elemento $ j $ che abbiamo trovato durante il passaggio 3, allora dobbiamo iniziare a ripetere alcuni Elemento nel passaggio 1. Quale elemento funzionerebbe come capo dell'elenco collegato in questo caso? In altre parole, nel passaggio 1, invece di cercare attraverso l'intero elenco, con quale elemento iniziamo a cercare?

ho trovato queste note di lezioni più facile da leggere rispetto al documento reale. Ho anche implementato una versione $ o (n^2) $ dell'algoritmo in Go qui, che chiunque può usare per fare riferimento. Tuttavia, vorrei un po 'di aiuto a ridurre la complessità a $ o (n) $. Qualsiasi aiuto sarebbe apprezzato!