Posts Tagged ‘subsequence’

Programming Praxis – Maximum Sum Subsequence

December 3, 2010

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.

Programming Praxis – Longest Common Subsequence

June 9, 2009

Today’s Programming Praxis problem is about finding the longest common subsequence of two sequences, and our target is 23 lines. Let’s go.

Our import:

import Data.Array

Hackage doesn’t seem to have an easily installable matrix package (hmatrix needs some C libraries), so we’re going to use an Array of Arrays to represent the grid of numbers. We’re going to define a little convenience function to access elements in the 2D array.

at :: Int -> Int -> Array Int (Array Int e) -> e
at x y a = a ! y ! x

And the longest common subsequence function itself.

lcs :: Eq a => [a] -> [a] -> [a]
lcs xs ys = reverse $ walk imax jmax where
    imax = length xs
    jmax = length ys
    ax = listArray (1, imax) xs
    ay = listArray (1, jmax) ys
    ls = listArray (0, jmax) [listArray (0, imax)
               [lcs' i j | i <- [0..imax]] | j <- [0..jmax]]

    lcs' 0 _ = 0
    lcs' _ 0 = 0
    lcs' i j | ax ! i == ay ! j = 1 + at (i-1) (j-1) ls
             | otherwise        = max (at (i-1) j ls) (at i (j-1) ls)

    walk 0 _ = []
    walk _ 0 = []
    walk i j | at (i-1) j ls == at i j ls = walk (i-1) j
             | at i (j-1) ls  < at i j ls = ax ! i : walk i (j-1)
             | otherwise                  = walk i (j-1)

And the usual test:

main :: IO ()
main = print $ lcs "programming" "praxis"

19 lines. Not much of an improvement. More importantly, the speed is far from optimal. The lcs in Data.List.LCS is considerably faster (though considerably longer). If anyone knows a better version, I’m all ears.