Posts Tagged ‘maximum’

Programming Praxis – Maximum Difference In An Array

April 1, 2011

In today’s Programming Praxis exercise, our goal is to find the maximum difference between two numbers in a list, with the condition that the higher number comes last. We need to write both a quadratic and a linear algorithm. Let’s get started, shall we?

Some imports:

import Data.List
import qualified Data.List.Key as K
import Data.Tuple.HT
import Test.QuickCheck

The quadratic number is a matter of finding the highest subsequent number for each number in the list and returning the pair with the greatest difference. The two reverse functions are needed since K.maximum unfortunately chooses the latter of the two elements when the comparison yields the same value.

maxDiffNaive :: (Enum a, Ord a, Num a) => [a] -> (a, a, a)
maxDiffNaive = K.maximum thd3 . reverse . map f . init . tails . zip [0..]
    where f xs = (i,j,hi-lo) where
                 (i,lo) = head xs
                 (j,hi) = K.maximum (subtract lo . snd) (reverse xs)

The linear version can be represented with a simple fold. The accumulator holds the current minimum value as well as the current maximum difference.

maxDiffSmart :: (Ord a, Num a, Enum a) => [a] -> (a, a, a)
maxDiffSmart = snd . (\(x:xs) -> foldl f (x,(0,0,0)) xs) . zip [0..]
    where f ((i',lo), (i,j,d)) (j',x) = (if x < lo then (j',x) else (i',lo),
              if x-lo > d then (i',j',x-lo) else (i,j,d))

Testing whether the two functions produce the same output can be easily automated using QuickCheck.

prop_maxDiff :: [Integer] -> Property
prop_maxDiff x = not (null x) ==> (maxDiffNaive x == maxDiffSmart x)

To test everything we use a combination of unit tests and QuickCheck.

main :: IO ()
main = do let test f = do print $ f [4,3,9,1,8,2,6,7,5] == (3,4,7)
                          print $ f [4,2,9,1,8,2,6,7,5] == (1,2,7)
                          print $ f [4,3,9,1,2,6,7,8,5] == (3,7,7)
                          print $ f [5,4,3] == (0,0,0)
                          print $ f [1,3,3] == (0,1,2)
          test maxDiffNaive
          test maxDiffSmart
          quickCheck prop_maxDiff

Everything seems to be working correctly.

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.