Content deleted Content added
No edit summary |
|||
Line 7:
==Algorithm==
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 algorithm uses [[dynamic programming]] to progressively build the final solution by incrementally solving progressively larger subsets of the problem. 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>.
Line 13:
: 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 list <math>I</math> is searched from right to left for the maximum value of <math>j</math> satisfying <math>L_j<L_k</math>
# If there is no such <math>j</math>, then add <math>I_k</math> to the end of the list.
# If there is such a <math>j</math>, and <math>R_j \geq R_k</math>, then add <math>I_k</math> to the end of the list.
# Otherwise (i.e., there is such a j, but <math>R_j < R_k</math>), extend the subsequence <math>I_k</math> to the left to encompass everything up to and including the leftmost score in <math>I_j</math>. Delete subsequences <math>I_j,I_j+1,...,I_k-1</math> from the list, and append <math>I_k</math> to the end of the list. Reconsider the newly extended subsequence <math>I_k</math> (now renumbered <math>I_j</math>) as in step 1.
:Once the end of the input is reached, all subsequences remaining on the list <math>I</math> are maximal.
Line 28 ⟶ 32:
total += s
if s > 0:
# store I[k] by (start,end) indices of scores
I[k] = (i,i+1)
Lidx[k] = i
Line 45 ⟶ 50:
k+=1
break;
# Getting maximal subsequences using stored indices
return [scores[I[l][0]:I[l][1]] for l in range(k)]
</source>
| |||