Maximum Segment Sum with Upper-Bounded Length
Shin-Cheng Mu
May 2007
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. This literate
Haskell script presents a program solving one of the
variations: computing the maximum sum of segments not longer
than an upper-bound.
The derivation uses the Thinning Theorem. Details are in
Mu (2007). The derived algorithm is similar to that of
Fan et al (2003).
Functions defined:
mssu_s :: Len -> [V] -> V
The specification.
mssu_l :: Len -> [V] -> V
Derived program, using lists in place of deques for expository
purpose.
mssu :: Len -> [V] -> V
Derived program, using Data.Edison.Seq.SimpleQueue.
QuickCheck properties:
test_ub :: Len
The upper-bound on the length of segments.
prop_mssu_l_correct :: [V] -> Bool
That mssu_l implements mssu_s.
prop_mssu_correct :: [V] -> Bool
That mssu implements mssu_s.
> import List
This program uses Edison. If you do not have Edison installed,
comment out the line below as well as the section for mssu.
> import qualified Data.Edison.Seq.SimpleQueue as Q
> import Test.QuickCheck
> type V = Integer
> type Len = Int
Specification. We assume that the type of values we deal
with is V. In general, V need not be restricted to Integer,
> mssu_s :: Len -> [V] -> V
> mssu_s ub = maxlist . map sum . filter ((ub >=) . length)
> . concat . map inits . tails
> maxlist :: Ord v => [v] -> v
> maxlist = foldr1 bmax
> x `bmax` y | x < y = y
> | otherwise = x
Derived algorithm, using lists in place of deques for expository
purpose.
> mssu_l :: Len -> [V] -> V
> mssu_l ub = snd. foldr (stepd_l ub) (((0,0),[]),0)
> type Deque a = [a]
> type SL = (V, Len)
> type ST = ((SL,Deque SL),V)
> stepd_l :: Len -> V -> ST -> ST
> stepd_l ub a (((s,l),xs),m) = (((a+s,1+l),ys), m `bmax` last' ys)
> where ys = (dropL_l neg' . dropR_l long') ((s,l):xs)
> neg' (b,n) = a + s - b < 0
> long' (b,n) = 1 + l - n > ub
> last' [] = 0
> last' xs = let (b,n) = last xs in a + s - b
> dropL_l = dropWhile
> dropR_l p [] = []
> dropR_l p xs | p (last xs) = dropR_l p (init xs)
> | otherwise = xs
Testing.
> test_ub = 4
> prop_mssu_l_correct x = mssu_s test_ub x == mssu_l test_ub x
> where types = x :: [V]
Derived algorithm, using a queue.
If you do not have Edison installed, comment out the rest
of the file.
> mssu :: Len -> [V] -> V
> mssu ub = snd. foldr (stepd ub) (((0,0),Q.empty),0)
> type STQ = ((SL,Q.Seq SL),V)
> stepd :: Len -> V -> STQ -> STQ
> stepd ub a (((s,l),xs),m) = (((a+s,1+l),ys), m `bmax` last' ys)
> where ys = (dropL neg' . dropR long') ((s,l) `Q.lcons` xs)
> neg' (b,n) = a + s - b < 0
> long' (b,n) = 1 + l - n > ub
> last' xs
> | Q.null xs = 0
> | otherwise = let (b,n) = Q.rhead xs in a + s - b
> dropL p xs = Q.dropWhile p xs
> dropR p xs
> | Q.null xs = xs
> | p (Q.rhead xs) = dropR p (Q.rtail xs)
> | otherwise = xs
> prop_mssu_correct x = mssu_s test_ub x == mssu test_ub x
> where types = x :: [V]
References
[FL03] T.-H. Fan, S. Lee, H.-I. Lu, T.-S. Tsou, T.-C. Wang, and
A. Yao. An optimal algorithm for maximum-sum segment and
its application in bioinformatics. In Proceedings of the
8th International Conference on Implementation and
Application of Automata (CIAA 2003), Lecture Notes in
Computer Science 2759, pages 46–66. Springer-Verlag, July
2003.
[Mu07] S-C. Mu. Maximum segment sum is back: deriving algorithms
for two maximum segment problems with bounded lengths.
Under submission. 2007.