Ruzzo–Tompa algorithm: Difference between revisions

Revision as of 04:03, 17 April 2018

Revision as of 04:35, 17 April 2018

Line 9:

==Algorithm==

There are several approaches to solving the all maximal scoring subsequences problem. A natural approach is to use existing, linear time algorithms (see [[maximum subarray problem]]) to find the maximum subsequence and then recursively find the maximal subsequences to the left and right of the maximum subsequence. This algorithm <math>O(n^2)</math> in the worst case. The analysis of this algorithm is similar to that of [[Quicksort]]: The maximum subsequence could be small in comparison to the rest of sequence. It is simple to build an example where this algorithm would be slow

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: