Maximum Difference In An Array

April 1, 2011

Today’s problem is this:

Given an array X, find the j and i that maximizes XjXi, subject to the condition that ij. If two different i,j pairs have equal differences, choose the “leftmost shortest” pair with the smallest i and, in case of a tie, the smallest j.

For instance, given an array [4, 3, 9, 1, 8, 2, 6, 7, 5], the maximum difference is 7 when i=3 and j=4. Given the array [4, 2, 9, 1, 8, 3, 6, 7, 5], the maximum difference of 7 appears at two points, but by the leftmost-shortest rule the desired result is i=1 and j=2. I and j need not be adjacent, as in the array [4, 3, 9, 1, 2, 6, 7, 8, 5], where the maximum difference of 7 is achieved when i=3 and j=7. If the array is monotonically decreasing the maximum difference is 0, which by the leftmost-shortest rule occurs when i=0 and j=0.

There are at least two solutions. The obvious solution that runs in quadratic time uses two nested loops, the outer loop over i from 0 to the length of the array n and the inner loop over j from i+1 to n, computing the difference between Xi and Xj and saving the result whenever a new maximum difference is found. There is also a clever linear-time solution that traverses the array once, simultaneously searching for a new minimum value and a new maximum difference; you’ll get it if you think about it for a minute.

Your task is to write both the quadratic and linear functions to compute the maximum difference in an array, and also a test function that demonstrates they are correct. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

20 Responses to “Maximum Difference In An Array”

  1. My Haskell solution (see http://bonsaicode.wordpress.com/2011/04/01/programming-praxis-maximum-difference-in-an-array/ for a version with comments):

    import Data.List
    import qualified Data.List.Key as K
    import Data.Tuple.HT
    import Test.QuickCheck
    
    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)
    
    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))
    
    prop_maxDiff :: [Integer] -> Property
    prop_maxDiff x = not (null x) ==> (maxDiffNaive x == maxDiffSmart x)
    
    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
    
  2. [...] today’s Programming Praxis exercise, our goal is to find the maximum difference between two numbers in a [...]

  3. Veer said

    I am having problem understanding of maximum difference in the above context.
    In array [4, 3, 9, 1, 8, 2, 6, 7, 5] how come max diff is 7 instead of 8 i.e 9-1 = 8
    and indices 2 <= 3 .
    Sorry if it is dumb question :D
    Cheers

  4. programmingpraxis said

    Veer: The task is to maximize Xj – Xi, subject to i <= j. That means the scan has to go from left to right.

  5. Veer said

    Thanks for clearing the doubt , I mistakenly read Xj – Xi as Xi – Xj .

  6. arturasl said

    Sorry, solution is quite big (I am new to this site – are there any posting limits?).
    My idea is to scan array from left to right and maintain two variable max and min. Min is the minimum element found so far, and max is maximum element found after min. Also then one of these changes, calculate difference and check if it is bigger than previous one. Everything seems to work :)

    #include      <iostream>
    #include      <cstdlib>
    #include      <ctime>
    
    std::pair<int, int> fnQuaratic(const int anArray[], int nSize) {
    	std::pair<int, int> result(0, 0);
    	int nMax = 0;
    
    	for (int i = 0; i < nSize; ++i) {
    		for (int j = i; j < nSize; ++j) {
    			if (nMax < anArray[j] - anArray[i]) {
    				nMax          = anArray[j] - anArray[i];
    				result.first  = i;
    				result.second = j;
    			}
    		}
    	}
    
    	return result;
    }
    
    std::pair<int, int> fnLinear(const int anArray[], int nSize) {
    	std::pair<int, int> result(0, 0);
    	int nMax = 0;
    	int nSmallest = anArray[0], nLargest = anArray[0];
    	int nSmallestPos = 0, nLargestPos = 0;
    
    	for (int i = 1; i < nSize; ++i) {
    		if (nSmallest > anArray[i]) {
    			nSmallest = anArray[i];
    			nSmallestPos = i;
    			nLargest = anArray[i];
    			nLargestPos = i;
    		}
    		if (nLargest < anArray[i]) {
    			nLargest = anArray[i];
    			nLargestPos = i;
    		}
    		if (nMax < nLargest - nSmallest) {
    			nMax          = nLargest - nSmallest;
    			result.first  = nSmallestPos;
    			result.second = nLargestPos;
    		}
    	}
    
    	return result;
    }
    
    int main(int argc, char **argv) {
    	int anArray[10];
    	const int nArray = sizeof(anArray) / sizeof(int);
    	std::pair<int, int> result1, result2;
    
    	srand(time(0));
    
    	for (int nTest = 1; nTest <= 1000000; ++nTest) {
    		for (int i = 0; i < nArray; ++i)
    			anArray[i] = rand() % 10 + 1;
    		if ((result1 = fnQuaratic(anArray, nArray)) == (result2 = fnLinear(anArray, nArray))){
    			for (int j = 0; j < nArray;  ++j) {
    				std::cout << anArray[j] << ' ';
    			}
    			std::cout << std::endl << result1.first << ", " << result1.second << std::endl;
    			std::cout << result2.first << ", " << result2.second << std::endl;
    		}
    	}
    	return 0;
    }
    
  7. arturasl said

    Instead of (result1 == result2) should be (result1 != result2) :D
    Additional idea – there is no need to save max. Instead of that simple check (anArray[i] – nSmallest). If (anArray[i] < nSmallest) then difference is negative number which is obliviously less than 0 (initial maximum). And if this difference is less than current maximum we can ignore it.

  8. Graham said

    @arturasi How does your fnLinear handle the monotonically
    decreasing case, e.g. [5, 4, 3, 2, 1]?

  9. Graham said

    @arturasl Sorry! I read the letter at the end of your name as an “i” instead of
    an “l.” Might need new glasses…

    I have to say I needed help finding the linear solution; brain’s a bit slow on
    Fridays I suppose. I’ve posted my solution on
    github.

  10. arturasl said

    @Graham, I don’t mind :) Probably I had to use capital L :D
    My fnLinear handles decreasing case correctly, because every time I change min value (which happens on every number in decreasing sequence) I also change max to min (because index of max number should be less or equal to min) which makes my procedure to check if maximum difference so far < 0. Which is always false as maximum difference so far is initialized to 0 by default. And so I get nSmallestPos = nLargestPos = nMax = 0.
    Any way as I said before all this can be simplified to github
    Which looks pretty much the same as your solution (taking into account my bad python skills :D )

  11. Toby said

    Here’s a SQL version.

    DROP TABLE IF EXISTS X;
    CREATE TABLE X (
    	idx INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
    	value INT NOT NULL
    );
    INSERT INTO X (value) VALUES (4),(3),(9),(1),(8),(2),(6),(7),(5);
    
    SELECT * FROM (
    	SELECT XI.idx-1 AS I, XJ.idx-1 AS J, XJ.value - XI.value AS diff
    	FROM X AS XI JOIN X AS XJ ON XI.idx <= XJ.idx
    ) Result ORDER BY diff DESC, I, J LIMIT 1;
    
     $ mysql -t test < maxdiff.sql 
    +---+---+------+
    | I | J | diff |
    +---+---+------+
    | 3 | 4 |    7 | 
    +---+---+------+
    
    
  12. Mike said

    This propblem is analogous to maximum subsequence sum problem.

    #
    # naive implementation.  O(n^2) complexity.
    #
    # Uses combinations(seq, k) from itertools library to returns all pairs of indices.
    # But, need to check for non-increasing input and return (0,0).
    #
    # The key for comparing differences is a 3-tuple (difference, -i, -j).  This causes
    # max() to break ties using the leftmost, shortest rule.
    #
    from itertools import combinations
    
    def max_diff1(lst):
        def key(t):
            i,j = t
            return lst[j]-lst[i], -i, -j
    
        i,j = max(combinations(range(len(lst)), 2), key=key)
    
        return (i, j) if lst[i] < lst[j] else (0, 0)
    
    #
    # smarter implementation.  O(n) complexity.
    #
    # Very similar to solution for max subsequence sum problem.  Keep track of the minimum value and index seen so far.
    # Calculate the difference between the current value and the minimum value so far.  And keep track of the maximum difference,
    # and corresponding differences.
    #
    # Used izip(seq, count()) instead of enumerate(seq) so that items sort correctly on the items value, not it's index.
    #
    # This version will work with iterables, not just lists.
    #
    from itertools import count, izip
    
    def max_diff2(seq):
        seq = izip(seq, count())
    
        floor = seq.next()
        diff = (0,0,0)
    
        for item in seq:
            floor = min(floor, item)
            delta = item[0] - floor[0], -floor[1], -item[1]
            best = max(delta, best)
    
        return -best[1], -best[2]
    
    testdata = [
        [4,3,9,1,8,2,6,7,5],
        [4,2,9,1,8,2,6,7,5],
        [4,3,9,1,2,6,7,8,5],
        [9,8,7,6,5,4,3,2,1]
        ]
    
    all(max_diff1(d[0]) == d[1] for d in testdata)
    
    all(max_diff2(d[0]) == d[1] for d in testdata)
    
    
  13. Rainer said

    My try in REXX

    
    a0 = '9, 8, 7, 6, 5, 4, 3, 2, 1'                             
    a1 = '4, 3, 9, 1, 8, 2, 6, 7, 5'                             
    a2 = '4, 2, 9, 1, 8, 3, 6, 7, 5'                             
    a3 = '4, 3, 9, 1, 2, 6, 7, 8, 5'                             
                                                                 
    a. = ''                                                      
                                                                 
    call create_array a1                                         
    d1 = maxdiff1(a1)                                            
    d2 = maxdiff2(a1)                                            
    if d1 \= d2 then say a1 '->' d1 '<->' d2                     
                                                                 
    call create_array a2                                         
    d1 = maxdiff1(a2)                                            
    d2 = maxdiff2(a2)                                            
    if d1 \= d2 then say a2 '->' d1 '<->' d2                     
                                                              
    call create_array a3                                      
    d1 = maxdiff1(a3)                                         
    d2 = maxdiff2(a3)                                         
    if d1 \= d2 then say a3 '->' d1 '<->' d2                  
    exit                                                      
                                                              
    maxdiff1: procedure expose a.                             
        retval = 0'|'1'|'1                                    
        diff = 0                                              
        do j = 1 to a.0                                       
            do k = j+1 to a.0                                 
                dn = a.k - a.j                                
                if dn > diff then do                          
                    diff = dn                                 
                    retval = diff'|'k'|'j                     
                end                                           
            end                                                     
        end                                                         
        parse value retval with diff'|'maxi'|'mini                  
        return 'Diff' diff 'Index' (maxi-1)'-Index' (mini-1)        
                                                                    
    maxdiff2: procedure expose a.                                   
        mini = 0                                                    
        maxi = 0                                                    
        diff = 0                                                    
        minp = 0                                                    
        maxp = 0                                                    
        retval = 0'|'1'|'1                                          
        do j = 1 to a.0                                             
            if j == 1 | a.j < mini then do                          
                mini = a.j                                          
                minp = j                                            
                maxi = 0                                            
            end                                                        
            if j == 1 | a.j > maxi then do                             
                maxi = a.j                                             
                maxp = j                                               
            end                                                        
            if (maxi-mini) > diff then do                              
                diff = maxi-mini                                       
                retval = diff'|'maxp'|'minp                            
            end                                                        
        end                                                            
        parse value retval with diff'|'maxi'|'mini                     
        return 'Diff' diff 'Index' (maxi-1)'-Index' (mini-1)           
                                                                       
    create_array: procedure expose a.                                  
        parse arg text                                                 
        a.= ''                                                         
        i = 0                                                          
        diff = 0                                          
        retval = ''                                       
        do while length(text) > 0                         
            parse value text with first','text            
            i = i+1                                       
            a.0 = i                                       
            a.i = first                                   
        end                                               
        return                                            
    
    
  14. schakra said

    #include
    #include

    int findMaxDiff(int *a, int size)
    {
    std::vector<std::pair > minmax(size);
    int min = a[0];
    int max = a[size - 1];
    for(int i = 0; i < size; i++)
    {
    if(a[i] max)
    max = a[size - 1 - i];
    minmax[i].first = min;
    minmax[size - 1 - i].second = max;
    }
    int maxDiff = minmax[0].second – minmax[0].first;
    for(int i = 1; i maxDiff)
    maxDiff = minmax[i].second – minmax[i].first;
    }
    return maxDiff;
    }

    int main()
    {
    int a[] = {4, 3, 9, 1, 8, 2, 6, 7, 5};
    std::cout << findMaxDiff(a, sizeof(a)/sizeof(int)) << std::endl;
    return 0;
    }

  15. Khanh Nguyen said

    In F#,

    open System
    
    let maxDiff (inp : int list) = 
    
        let aux (left, right, min_pos) (pos, v) =
            if (v - inp.[min_pos]) > (inp.[right] - inp.[left]) then
                (min_pos, pos, min_pos)
            else
                if (v < inp.[min_pos]) then (left, right, pos) else (left, right, min_pos)
    
        let n = List.length inp
        let (l, r, m) = List.fold aux (0, 0, 0) (List.zip [0..(n-1)] inp)
        (l,r, inp.[r] - inp.[l])
    
    maxDiff [4; 3; 9; 1; 8; 2; 6; 7; 5]
    maxDiff [4; 2; 9; 1; 8; 3; 6; 7; 5]
    maxDiff [4; 3; 9; 1; 2; 6; 7; 8; 5]
    maxDiff [5;4;2]
  16. yaq said

    I am trying to embed code through gist, but it’s not displayed. I just paste the raw text here.

    (define (enumerate-interval low high)
    (if (> low high)
    ‘()
    (cons low (enumerate-interval (+ low 1) high))))

    (define (accumulate op initial sequence)
    (if (null? sequence)
    initial
    (op (car sequence)
    (accumulate op initial (cdr sequence)))))

    (define (last-index l)
    (- (length l) 1))

    (define (get-diff data j i)
    (- (list-ref data j) (list-ref data i)))

    (define (get-value result)
    (car result))

    (define (get-i result)
    (cadr result))

    (define (get-j result)
    (caddr result))

    (define (max-diff-internal max data)
    (cond ((null? data) max)

    ((< (get-value max) (get-value (car data)))
    (max-diff-internal (car data) (cdr data)))

    ((= (get-value max) (get-value (car data)))
    (cond (( (get-i max) (get-i (car data)))
    (max-diff-internal (car data) (cdr data)))
    (else
    (cond ((< (get-j max) (get-j (car data)))
    (max-diff-internal max (cdr data)))
    (else
    (max-diff-internal (car data) (cdr data)))))))
    (else
    (max-diff-internal max (cdr data)))))

    (define (max-diff data)
    (let ((diff-result (accumulate append
    '()
    (map (lambda (i)
    (map (lambda (j) (list (get-diff data j i) i j))
    (enumerate-interval i (last-index data))))
    (enumerate-interval 0 (last-index data))))))
    (max-diff-internal (car diff-result) diff-result)))

    (max-diff (list 4 3 9 1 8 2 6 7 5))

    ;linear-time solution
    ;result is a list contains (max-diff-value i j)
    (define (max-diff-iter k min-i result data)
    (cond ((= k (length data)) result)
    (else
    (let* ((new-min-i (if ( diff (get-value result))
    (list diff new-min-i k)
    result)))
    (max-diff-iter (+ k 1) new-min-i new-result data)))))

    (define (max-diff-test)
    (assert (max-diff (list 4 3 9 1 8 2 6 7 5)) (list 7 3 4))
    (assert (max-diff (list 4 2 9 1 8 3 6 7 5)) (list 7 1 2))
    (assert (max-diff (list 4 3 9 1 2 6 7 8 5)) (list 7 3 7))
    (assert (max-diff (list 5 4 3)) (list 0 0 0))
    (assert (max-diff (list 1 3 3)) (list 2 0 1))
    (assert (max-diff-iter 0 0 (list 0 0 0) (list 4 3 9 1 8 2 6 7 5)) (list 7 3 4))
    (assert (max-diff-iter 0 0 (list 0 0 0) (list 4 2 9 1 8 3 6 7 5)) (list 7 1 2))
    (assert (max-diff-iter 0 0 (list 0 0 0) (list 4 3 9 1 2 6 7 8 5)) (list 7 3 7))
    (assert (max-diff-iter 0 0 (list 0 0 0) (list 5 4 3)) (list 0 0 0))
    (assert (max-diff-iter 0 0 (list 0 0 0) (list 1 3 3)) (list 2 0 1)))

    (max-diff-test)

  17. yaq said

    This is the formatted one, please ignore or delete my previous comment

    praxis.ss

    (define (enumerate-interval low high)
      (if (> low high)
          '()
          (cons low (enumerate-interval (+ low 1) high))))
    
    (define (accumulate op initial sequence)
      (if (null? sequence)
          initial
          (op (car sequence)
              (accumulate op initial (cdr sequence)))))
    
    (define (last-index l)
      (- (length l) 1))
    
    (define (get-diff data j i)
      (- (list-ref data j) (list-ref data i)))
    
    (define (get-value result)
      (car result))
    
    (define (get-i result)
      (cadr result))
    
    (define (get-j result)
      (caddr result))
    
    (define (max-diff-internal max data)
      (cond ((null? data) max)
            
            ((< (get-value max) (get-value (car data)))
             (max-diff-internal (car data) (cdr data)))
            
            ((= (get-value max) (get-value (car data)))
             (cond ((< (get-i max) (get-i (car data)))
                    (max-diff-internal max (cdr data)))
                   ((> (get-i max) (get-i (car data)))
                    (max-diff-internal (car data) (cdr data)))
                   (else
                    (cond ((< (get-j max) (get-j (car data)))
                           (max-diff-internal max (cdr data)))
                          (else 
                           (max-diff-internal (car data) (cdr data)))))))
            (else
             (max-diff-internal max (cdr data)))))
    
    
    (define (max-diff data)
      (let ((diff-result (accumulate append
                                     '()
                                     (map (lambda (i)
                                            (map (lambda (j) (list (get-diff data j i) i j))
                                                 (enumerate-interval i (last-index data))))
                                          (enumerate-interval 0 (last-index data))))))
        (max-diff-internal (car diff-result) diff-result)))
    
    
    (max-diff (list 4 3 9 1 8 2 6 7 5))
    
    ;linear-time solution
    ;result is a list contains (max-diff-value i j)
    (define (max-diff-iter k min-i result data)
      (cond ((= k (length data)) result)
            (else
             (let* ((new-min-i (if (< (list-ref data k) (list-ref data min-i))
                                   k
                                   min-i))
                    (diff (get-diff data k new-min-i))
                    (new-result (if (> diff (get-value result))
                                    (list diff new-min-i k)
                                    result)))
               (max-diff-iter (+ k 1) new-min-i new-result data)))))
    
    (define (max-diff-test)
      (assert (max-diff (list 4 3 9 1 8 2 6 7 5)) (list 7 3 4))
      (assert (max-diff (list 4 2 9 1 8 3 6 7 5)) (list 7 1 2))
      (assert (max-diff (list 4 3 9 1 2 6 7 8 5)) (list 7 3 7))
      (assert (max-diff (list 5 4 3)) (list 0 0 0))
      (assert (max-diff (list 1 3 3)) (list 2 0 1))
      (assert (max-diff-iter 0 0 (list 0 0 0) (list 4 3 9 1 8 2 6 7 5)) (list 7 3 4))
      (assert (max-diff-iter 0 0 (list 0 0 0) (list 4 2 9 1 8 3 6 7 5)) (list 7 1 2))
      (assert (max-diff-iter 0 0 (list 0 0 0) (list 4 3 9 1 2 6 7 8 5)) (list 7 3 7))
      (assert (max-diff-iter 0 0 (list 0 0 0) (list 5 4 3)) (list 0 0 0))
      (assert (max-diff-iter 0 0 (list 0 0 0) (list 1 3 3)) (list 2 0 1)))
    
    (max-diff-test)
    

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 627 other followers

%d bloggers like this: