In today’s Programming Praxis exercise, we have to implement four different ways of solving the problem of finding the contiguous subsequence with the maximum sum from a list, each with a different big O complexity. Let’s get started, shall we?

A quick import:

import Data.List

The O(n^3) version is simple: generate all the contiguous subsequences and find the one with the highest sum.

maxSum1 :: (Ord a, Num a) => [a] -> a maxSum1 xs = maximum . map sum $ inits =<< tails xs

The previous algorithm can be improved by keeping track of the sum during the subsequence generation, reducing it to O(n^2).

maxSum2 :: (Ord a, Num a) => [a] -> a maxSum2 xs = maximum $ scanl (+) 0 =<< tails xs

The O(n log n) one is a lot more tricky, and took me a couple of tries. In the end, I decided to things things bottom-up rather than the Scheme solution’s top-down approach. We start by converting each number to a list of length 1 with a sum equal to itself. Then we keep merging these list pairwise until we only have one element left. The merging is the same as in the Scheme solution: the new maximum sum is equal to the maximum of those of the two subsequences and the maximum sum that can be obtained after the concatenation.

maxSum3 :: (Ord a, Num a) => [a] -> a maxSum3 = fst . head . until (null . tail) f . map (\x -> (x, [x])) where f ((lm, l):(rm, r):xs) = (maximum [maximum (scanl (+) 0 r) + maximum (scanr (+) 0 l), lm, rm], l ++ r) : f xs f xs = xs

The O(n) solution is easier to write, and can be done with a simple fold.

maxSum4 :: (Ord a, Num a) => [a] -> a maxSum4 = snd . foldl (\(here, sofar) x -> let m = max 0 $ here + x in (m, max m sofar)) (0, 0)

Some tests to see if everything is working properly:

main :: IO () main = do let test f = print $ f [31,-41,59,26,-53,58,97,-93,-23,84] == 187 test maxSum1 test maxSum2 test maxSum3 test maxSum4

Yep. I have to admit though, I wouldn’t have come up with the O(n log n) or O(n) version during an interview, and maybe not even the O(n^2) version. I would have assumed there would be a more efficient algorithm, but having never needed to solve this problem before nor having read Programming Pearls I wouldn’t have been able to give the exact lower bound. I Guess I won’t be working for Phil any time soon Then again, I personally believe that, in an age where efficient algorithms for problems like this are a five-second Google search away, an encyclopedic knowledge of efficient algorithms is nice to have but hardly essential.

Tags: bonsai, code, Haskell, kata, maximum, praxis, programming, subsequence, sum

December 3, 2010 at 2:30 pm |

See http://www.iis.sinica.edu.tw/~scm/2010/maximum-segment-sum-origin-and-derivation/ for a beautiful derivation of the linear solution.

See also Chapter 11 of Pearls of Functional Algorithm Design (R. Bird) for a solution to the maximum non-segment sum.

December 15, 2010 at 8:51 pm |

For some reason, I’ve had a mental block about monads, but this example has given me the insights I have been missing to really grok how to use them. I still have a ways to go, but this example gave me a good starting point. Thanks!

December 16, 2010 at 12:37 am |

Happy to help Though to be honest, I don’t understand why everyone always makes such a big deal about monads. It’s nothing more than a type class that defines two functions. The Num class defines 6, but nobody makes a fuss about that. For lists >>= is nothing more than a shorter synonym for concatMap, which is the main reason I use it here. Haskell has plenty of aspects that are complicated; for example 99% of the stuff Oleg does hurts my head. Monads are trivial by comparison.

December 20, 2010 at 5:26 pm |

At a guess, it’s because until you hit monads, typeclasses don’t seem to be a terribly big deal. Once you hit monads, you start seeing them EVERYWHERE.