It may be surprising that variations of the maximum segment sum (MSS) problem, a textbook example for the squiggolists, are still active topics for algorithm designers. These literate Haskell scripts presents a program solving two recently studied variations:
- mssu.lhs: an amortised linear-time algorithm computing the maximum sum of segments not longer than an upper-bound;
- msdlb.lhs: an O(n log L) algorithm computing the maximum density (average) of segments not shorter than a lower-bound;
- msdll.lhs: computing the maximum density (average) of segments not shorter than a lower-bound. With the discovery of Glodwasser et al. we are able to refine the algorithm to amortised linear time again.
2007/06/26 Update: fixed binary search.
2007/11/04 Update: linear time algorithm for MSDL.