Programming Praxis – Maximum Sum Subsequence

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.

About these ads

Tags: , , , , , , , ,

4 Responses to “Programming Praxis – Maximum Sum Subsequence”

  1. Benoît Huron Says:

    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.

  2. Eric the Read Says:

    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!

  3. Remco Niemeijer Says:

    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.

  4. Eric the Read Says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: