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!

up vote 1 down vote accepted
+100

What element would operate as the head of the linked list in this case?

That's of course $L_{k-1}$.

If you are surprised why this works in $O(n)$, that paper has already explained:

Once a list element has been by-passed by this chain, it will be examined again only if it is being deleted from the list, either in Step 2 or Step 4. The work done in the “reconsider” loop of Step 4 can be amortized over the list item(s) being deleted. Hence, in effect, each list item is examined a bounded number of times, and the total running time is linear.


Let's consider the example given in the paper. The sequence is $(4, -5, 3, -3, 1, 2, -2, 2, -2, 1, 5)$. The list is initially empty. The first subsequence $(4)$ comes, we keep a pointer to the head of the list, like

H <- (4)

Next, we sWe add it to the end of the list. We search $I_1$ and find $L_1>L_2$, so we keep a pointer to the head, like

H <- (4)  (3)
^         /
 \       /
  -------

Next, we skip $-3$ and the subsequence $(1)$ comes. We search $I_2$ and find $L_2=L_3$. Since $I_2$ points to the head, we assert there is no such $j$ such that $L_j<L_3$ and keep a pointer to the head, like

H <- (4)  (3)  (1)
^         /    /
 \       /    /
  ------------

Next, the subsequence $(2)$ comes. We search $I_3$ and find $L_3<L_4, R_3<R_4$, so we apply step 4 and get (note $I_3$ need to be reconsidered after merging while no change is needed here since it points to the head)

H <- (4)  (3)  (1,2)
^         /    /
 \       /    /
  ------------

Next, we skip $-2$ and the subsequence $(2)$ comes. We search $I_3$ and find $L_3<L_4, R_3=R_4$, so we keep a pointer to $I_3$, like

H <- (4)  (3)  (1,2) <- (2)
^         /    /
 \       /    /
  ------------

Next, we skip $-2$ and the subsequence $(1)$ comes. We search $I_4$ and find $L_4=L_5$, then search $I_3$ and find $L_3<L_5, R_3>R_5$. We keep a pointer to $I_3$, like

H <- (4)  (3)  (1,2) <- (2)  (1)
^         /    /  ^          /
 \       /    /    \        /
  ------------      --------

Next, the last subsequence $(5)$ comes. We search $I_5$ and find $L_5<L_6, R_5<R_6$, then we merge $I_5$ and $I_6$ and get

H <- (4)  (3)  (1,2) <- (2)  (1,5)
^         /    /  ^          /
 \       /    /    \        /
  ------------      --------

Note $I_5$ needs to be reconsidered. Since $I_5$ points to $I_3$, we search $I_3$ first and find $L_3<L_5, R_3<R_5$, so we merge $I_3,I_4,I_5$ and get

H <- (4)  (3)  (1,2,−2,2,−2,1,5)
^         /    / 
 \       /    /  
  ------------      

We then reconsider $I_3$ and no change is needed since it points to the head.

  • Could you provide an example with the linked list in action? It would help to see how it operates in $O(n)$. – Shrey Jun 21 at 18:23
  • @Shrey I have added an example. – xskxzr Jun 22 at 5:12
  • This is very helpful. Thank you so much for your help! – Shrey Jun 22 at 6:08

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.