## Maximum Difference In An Array

### April 1, 2011

We begin with the quadratic-time solution. Nested loops on i and j consider all possibilities, and variables lo, hi and diff are updated whenever a larger difference is found:

```(define (max-diff-quadratic xv)   (define (x n) (vector-ref xv n))   (let ((len (vector-length xv)))     (let ((lo 0) (hi 0) (diff 0))       (do ((i 0 (+ i 1))) ((= i len) (list lo hi diff))         (do ((j (+ i 1) (+ j 1))) ((= j len))           (let ((d (- (x j) (x i))))             (when (< diff d)               (set! lo i) (set! hi j) (set! diff d))))))))```

In the linear-time solution, k loops over the input vector, touching each element once. Lo, hi and max-d track the current maximum difference, min-lo tracks the minimum value seen so far, which may potentially be the site of a new lo if a corresponding hi with a difference greater than the current difference can be found. and d is the difference from min-lo at the current location:

```(define (max-diff-linear xv)   (define (x n) (vector-ref xv n))   (let loop ((k 0) (lo 0) (hi 0) (min-lo 0) (max-d 0))     (if (= (vector-length xv) k)         (list lo hi max-d)         (let* ((min-lo (if (< (x k) (x min-lo)) k min-lo))                (d (- (x k) (x min-lo))))           (if (< max-d d)               (loop (+ k 1) min-lo k min-lo d)               (loop (+ k 1) lo hi min-lo max-d))))))```

For testing we explicitly test all the examples given in the problem definition, plus 1000 length-25 vectors chosen at random, plus 25 length-1000 vectors chosen at random:

```(define (max-diff-test)   (assert (max-diff-quadratic #(4 3 9 1 8 2 6 7 5)) '(3 4 7))   (assert (max-diff-quadratic #(4 2 9 1 8 3 6 7 5)) '(1 2 7))   (assert (max-diff-quadratic #(4 3 9 1 2 6 7 8 5)) '(3 7 7))   (assert (max-diff-quadratic #(5 4 3)) '(0 0 0))   (assert (max-diff-quadratic #(1 3 3)) '(0 1 2))   (assert (max-diff-linear #(4 3 9 1 8 2 6 7 5)) '(3 4 7))   (assert (max-diff-linear #(4 2 9 1 8 3 6 7 5)) '(1 2 7))   (assert (max-diff-linear #(4 3 9 1 2 6 7 8 5)) '(3 7 7))   (assert (max-diff-linear #(5 4 3)) '(0 0 0))   (assert (max-diff-linear #(1 3 3)) '(0 1 2))   (do ((i 0 (+ i 1))) ((= i 1000))     (let ((x (list->vector (shuffle (range 1 25)))))       (assert (max-diff-quadratic x) (max-diff-linear x))))   (do ((i 0 (+ i 1))) ((= i 25))     (let ((x (list->vector (shuffle (range 1 1000)))))       (assert (max-diff-quadratic x) (max-diff-linear x)))))```

Range, assert, randint and shuffle are from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/SlkN9AOJ.

Pages: 1 2

### 22 Responses to “Maximum Difference In An Array”

```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
(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, nLargest = anArray;
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;
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 - floor, -floor, -item
best = max(delta, best)

return -best, -best

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) == d for d in testdata)

all(max_diff2(d) == d 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;
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.second – minmax.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)

(define (get-j 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)

(define (get-j 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)
```
18. […] similar problem: find the maximum difference of two numbers in an array max difference […]

19. frame said

Javascript solution:

```function maxDiff(arr){

var minI = 0;
for ( var i in arr )
if ( arr[i] < arr[minI] )
minI = i;

var maxD = 0;
var d;
for ( i = 0 ;i < arr.length; i++ )
if ( arr[minI] < arr[i] && minI  maxD )
maxD = d;

return maxD;

}

maxDiff( [9,8,7,6,5,4]);
```