Content deleted Content added
No edit summary |
|||
Line 22:
:Once the end of the input is reached, all subsequences remaining on the list <math>I</math> are maximal.<ref name="ruzzo_tompa"></ref>
As example of the algorithm running, consider the input score list <math>L=[4,-5,3,-2,1,2]</math>. On input <math>4</math> in step 1, no satisfying <math>j</math> is found so step 2 applies and <math>[4]</math> is appended to <math>I</math>, so <math>I=[[4]], R=[4], L=[0]</math>. The input <math>-5</math> is skipped and the input <math>3</math> is read. In step 1, no satisfying <math>j</math> is found so <math>[3]</math> is appended to <math>I</math>, so <math>I=[[4],[3]], R=[4,2], L=[0,-1]</math>. The input <math>-2</math> is skipped and the input <math>1</math> is read. In step 1, a value of <math>j=1</math> is found to satisfy <math>L[j]<L[k]</math>, so step 3 applies. In step 3, <math>R[j]\ngeq R[k]</math>, so <math>[1]</math> is appended to <math>I</math>, and now <math>I=[[4],[3],[1]], R=[4,2,1], L=[0,-1,0]</math>. On input <math>2</math> in step 1 a value of <math>j=4</math> is found to satisfy <math>L[j]<L[k]</math>, so step 3 applies. In step 3, <math>R[j]\geq R[k]</math>, so step 4 applies. In step 4, the elements of <math>I[j]</math> are inserted into <math>I[k]</math> and <math>I[j]</math> is removed from <math>I</math>, so now <math>I=[[4],[3]], R=[4,2], L=[0,-1]. Now we consider the input <math>I[k]=[1,2]</math>. In step 1, a value of <math>j=1</math> is found to satisfy <math>L[j]<L[k]</math>, so step 3 applies. In step 3, <math>R[j]\geq R[k]</math>, so step 4 applies. In step 4, the elements of <math>I[j]</math> are inserted into <math>I[k]</math> and <math>I[j]</math> is removed from <math>I</math>, so now <math>I=[[4]], R=[4], L=[0]. Now we consider the input <math>I[k]=[3,-2,1,2]</math>. In step 1, so satisfying value of <math>j</math> is found, so <math>[3,-2,1,2]</math> is appended to <math>I</math>. The end of the input has been reached, so the final value of <math>I</math> is <math>[[4],[3,-2,1,2]].
The following [[Python (programming language)|Python]] code implements the Ruzzo-Tompa algorithm:
| |||