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:
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.