An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation

Daniel Lemire, Martin Brooks, Yuhong Yan

Monotonicity is a simple yet significant qualitative characteristic. We consider the problem of segmenting an array in up to K segments. We want segments to be as monotonic as poss…