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.