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: computing the maximum sum of segments not longer than an upper-bound, and the maximum density (average) of segments not shorter than a lower-bound. 2007/06/26 Update: fixed binary search.
2007/11/04 Update: linear time algorithm for MSDL.
Research
Agda Approximation Bidirectional Updating Burrows-Wheeler Transform Concurrency Converse-of-a-Function Theorem Curry-Howard Data Structure Dependent Type Fibonacci GADT Galois Connection Greedy Theorem Haskell HaXML Imperative Programs Indirect Equality List Homomorphism Logic Logic Programming Optimisation Problems Program Derivation Program Inversion Quantum Programming Quine Regular Expression Segment Problems Termination Thinning Theorem Types XML Streaming λ calculusRecent Comments
- Matt on A Survey of Binary Search
- Shin on The Maximum Segment Sum Problem: Its Origin, and a Derivation
- Shin on The Maximum Segment Sum Problem: Its Origin, and a Derivation
- minime on Beamer Article Mode Does Not Save Paper?
- wren ng thornton on Proving the Church-Rosser Theorem Using a Locally Nameless Representation