Programming Praxis – Maximum Difference In An Array

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.

About these ads

Tags: , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: