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</math>, 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 lists are initially empty. Scores are read from left to right and are processed as follows. Nonpositive scores are require no special processing, so the next score is read. A positive score is incorporated into a new sub-sequence <math>I_k</math> of length one that is then integrated into the list by the following process.
The following [[Python (programming language)|Python]] code implements the Ruzzo-Tompa algorithm:
| |||