Posts Tagged ‘difference’

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.