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: bonsai, code, Haskell, kata, maximum, praxis, programming, subsequence, sum