Is this the same as Kadane's maximum-subarray algorithm?

No. The standard maximum-subarray task returns one best interval; Ruzzo - Tompa targets the full maximal collection.

Can a returned interval contain negative numbers?

Yes, when the entire interval satisfies the maximality rules.

Does linear time mean constant memory?

No. The original worst-case storage bound is also linear, although early output can reduce practical memory use.

AI Glossary / Mathematics and optimization / Advanced

Ruzzo - Tompa algorithm

Definition

The Ruzzo - Tompa algorithm finds all maximal scoring contiguous subsequences in a sequence of real-valued scores, using linear time when implemented with its prescribed bookkeeping. Each returned interval has a positive total score, and the intervals do not overlap. The algorithm was introduced by Walter L. Ruzzo and Martin Tompa for identifying multiple interesting regions in biological sequences.

What it means

Here subsequence means consecutive entries: positions cannot be skipped inside an interval. The aim differs from finding only the single highest-scoring interval, and from listing every interval above a threshold. Maximal has a precise technical definition. Conceptually, choose a highest-scoring positive interval, then repeat in the remaining portions, excluding zero-scoring extensions at its ends. The resulting collection captures distinct regions instead of repeatedly returning nearly identical overlapping versions of one strong region. Output order can follow sequence position rather than descending score.

How it works

Read the scores from left to right while maintaining their cumulative total and a list of candidate intervals. For each candidate, store cumulative totals immediately before its start and at its end. A positive score starts a candidate; comparisons of these boundary totals determine whether it should remain separate or merge with earlier candidates and the intervening scores. Nonpositive values still affect the cumulative total even though they do not start candidates. Crucially, the linear-time implementation uses links that avoid repeatedly scanning the same candidates. A straightforward repeated scan of the whole list does not inherit the linear-time bound. Final candidates identify the required intervals; the original paper also describes when some intervals can be emitted early.

Three practical examples

A biological-sequence analysis can assign residue scores for a composition of interest and locate several candidate regions for subsequent investigation.
A synthetic monitoring experiment can assign positive and negative evidence scores to ordered observations and explore which contiguous intervals accumulate strong evidence. This requires a separately justified scoring model.
An algorithm-testing project can compare an efficient implementation against exhaustive interval enumeration on short sequences, including zero scores and tied sums. The exhaustive method is useful for checking correctness even though it is unsuitable for very long inputs.

Think of it this way

Think of finding profitable stretches along an ordered route whose stops can add gains or losses. A small loss may be worth crossing to connect two strong stretches, but a large loss can keep them separate. The analogy explains why taking only runs of positive numbers is insufficient. The algorithm operates on additive scores and its specific maximality rules, not on a real route's travel constraints or a general business profit model.

Worked example

Consider scores [4, −1, 3, −10, 2, −1, 2]. The interval at positions 1-3 totals 6, and the interval at positions 5-7 totals 3. The −1 inside each is worth retaining: splitting the first would give separate scores 4 and 3, while splitting the second gives 2 and 2. Under the maximal-interval definition, the merged intervals are preferred because their individual totals exceed those of their proper contiguous parts. The −10 between them prevents a beneficial larger interval; the total across positions 1-7 is −1. Cumulative totals, including the initial zero, are [0, 4, 3, 6, −4, −2, −3, −1]. Subtraction confirms the scores: 6 − 0 = 6 and −1 − (−4) = 3. The returned intervals are therefore 1-3 and 5-7. Their combined score is 9, but choosing all positive singleton positions would total 11. This demonstrates that the problem is not unrestricted maximization of the sum across an arbitrary collection of disjoint intervals. It has the stated maximal-region definition.

Illustrative case study

In a fictional project, Juniper Sequence Lab builds an exploratory region finder using fixed residue scores. Before processing long sequences, the developers check short hand-calculated examples and compare interval boundaries with an exhaustive reference implementation. Researchers then evaluate candidate regions with independent biological evidence. They do not treat a high score as automatic proof of a biological function. The case illustrates a validation workflow without claiming discovery rates, speed measurements or experimentally established biological results.

Common misconceptions and mistakes

Maximal and maximum are not interchangeable here: several returned regions may have different scores. Simply saying that a region cannot be extended to improve its score is not a complete definition; the original paper gives a subtler characterization. Negative entries can belong inside a returned interval. Conversely, an all-nonpositive sequence produces no positive-scoring output. Zero-sum prefixes and suffixes require the paper's tie convention, rather than arbitrary extension of boundaries. Floating-point rounding can change comparisons near zero, so numerical conventions should be tested and documented.

Business use

Use the algorithm when the desired output is several distinct contiguous regions under an additive score system. Validate the score assignment independently from the search procedure. Preserve positions, interval totals and the scoring-model version so results remain interpretable. If analysts need a fixed number of intervals, minimum lengths, gap penalties or a different overlap rule, check whether that changes the optimization problem; the original guarantee does not automatically cover such modifications. For significance claims, add an appropriate statistical analysis rather than converting a raw interval score directly into a probability.

Check your understanding

In the worked sequence, should the first −1 automatically separate scores 4 and 3?

Answer: No. Their combined contiguous interval has score 6 and forms one maximal region under the stated definition.

Related terms

Log likelihood ratio
maximum subarray
prefix sum
sequence analysis
amortized analysis
interval scoring

Learn next

enumerate every interval in the seven-score example and check its total by prefix subtraction. Then examine [3, 0] to see why zero-sum boundary extensions need a tie convention. Study the linking optimization before claiming an implementation runs in linear time.

Sources

Sources: Walter L. Ruzzo and Martin Tompa, A Linear Time Algorithm for Finding All Maximal Scoring Subsequences, https://homes.cs.washington.edu/~ruzzo/papers/maxseq.pdf ; authors' publication record, https://homes.cs.washington.edu/~ruzzo/papers/maxseq.html . The seven-score example and fictional laboratory are original. The input worklist's damaged dash is preserved in metadata; the standard spelling is Ruzzo–Tompa.

Previous: Run-length encoding Next: RVQ