Contiguous Sequence

In [1]:

    

import Data.List
import Data.Maybe


    

In [2]:

    

contiguousSequence :: (Ord a, Num a) => [a] -> Maybe a
contiguousSequence xs =
    let computeState :: (Ord a, Num a) => (Maybe a, a) -> a -> (Maybe a, a)
        computeState (oldBest, oldCurrent) x = (newBest, newCurrentOrZero)
            where
                newCurrent = oldCurrent + x
                newBest = Just $ maximum $ newCurrent : catMaybes [oldBest]
                newCurrentOrZero = max 0 newCurrent
    in fst $ foldl' computeState (Nothing, 0) xs


    

In [3]:

    

contiguousSequence [2, -8, 3, -2, 4, -10]


    

    





Just5

In [4]:

    

import Test.QuickCheck


    

In [5]:

    

contiguousSequence' :: (Ord a, Num a) => [a] -> Maybe a
contiguousSequence' [] = Nothing
contiguousSequence' xs =
    Just $ maximum $ map sum $ filter (not . null) $ filter (`isInfixOf` xs) $ subsequences xs


    

In [6]:

    

testContiguousSequence :: (Ord a, Num a) => [a] -> Bool
testContiguousSequence xs =
    contiguousSequence xs == contiguousSequence' xs


    

In [7]:

    

quickCheckWith stdArgs { maxSize = 25 } testContiguousSequence


    

    






+++ OK, passed 100 tests.

In [8]:

    

contiguousSequence'' :: (Ord a, Num a) => [a] -> Maybe a
contiguousSequence'' [] = Nothing
contiguousSequence'' xs = Just $ maximum $ map sum $ concatMap (tail . inits) $ init $ tails xs


    

In [9]:

    

testContiguousSequence' :: (Ord a, Num a) => [a] -> Bool
testContiguousSequence' xs =
    contiguousSequence xs == contiguousSequence'' xs


    

In [10]:

    

quickCheck testContiguousSequence'


    

    






+++ OK, passed 100 tests.