Ruzzo–Tompa algorithm (original) (raw)

The Ruzzo–Tompa algorithm is a linear-time algorithm for finding all non-overlapping, contiguous, maximal scoring subsequences in a sequence of real numbers. This algorithm is an improvement over previously known quadratic time algorithms. The maximum scoring subsequence from the set produced by the algorithm is also a solution to the maximum subarray problem. The Ruzzo–Tompa algorithm has applications in bioinformatics, web scraping, and information retrieval.