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.