An Optimal Algorithm for the Maximum-Density Segment Problem

Kai-min Chung, Hsueh-I Lu

We address a fundamental problem arising from analysis of biomolecular sequences. The input consists of two numbers $w_{\min }$ and $w_{\max }$ and a sequence $S$ of $n$ number pairs…