*Bounty: 100*

*Bounty: 100*

For a project, I’m implementing the All Maximal Scoring Subsequences algorithm. In the analysis portion of the paper, it describes an optimization that makes the algorithm run in linear time. Namely, when doing the search for the rightmost value of $j$ that satisfies $L_j < L_k$, we can search a linked list with monotonically decreasing $L_j$ values.

I’m slightly confused on how this works. If we store a pointer to the element $j$ we found during Step 3, then we must start iterating with *some* element in Step 1. What element would operate as the head of the linked list in this case? In other words, in Step 1, instead of searching through the whole list, what element do we start searching with?

I found these lectures notes easier to read than the actual paper. I also implemented a $O(n^2)$ version of the algorithm in Go here, which anyone may use to reference. However, I would like some help cutting the complexity down to $O(n)$. Any help would be appreciated!