Content deleted Content added
No edit summary |
|||
Line 9:
The standard implementation of the Ruzzo-Tompa algorithm runs in <math>O(n)</math> time and uses <math>O(n)</math> space, where <math>n</math> is the length of the list of scores. The description of the algorithm provided by Ruzzo and Tompa is as follows:
: Read the scores left to right and maintain the cumulative sum of the scores read. Maintain an ordered list <math>I_1,I_2,...,I_j</math> of disjoint subsequences. For each subsequence <math>I_j, record the cumulative total <math>L_j</math> of all scores up to but not including the leftmost score of <math>I_j</math>, and the total <math>R_j</math> up to and including the rightmost score of <math>I_j</math>.
The following [[Python (programming language)|Python]] code implements the Ruzzo-Tompa algorithm:
Line 41 ⟶ 42:
return [scores[I[l][0]:I[l][1]] for l in range(k)]
</source>
== References ==
| |||