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

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