Largest Forward Difference

January 20, 2015

The obvious brute-force solution computes all differences and takes the largest:

(define (largest-forward-difference xs)
  (let ((lfd 0))
    (do ((xs xs (cdr xs))) ((null? xs) lfd)
      (do ((ys xs (cdr ys))) ((null? ys))
        (set! lfd (max lfd (- (car ys) (car xs))))))))

This takes O(n2) time and O(1) space. Here are some examples:

> (largest-forward-difference '(1 5 7 2 9))
8
> (largest-forward-difference '(4 3 2 1))
0

A better solution scans the array from left to right. After initializing with the first two integers in the array, at each step during a left-to-right scan of the remainder of the array the largest forward difference is either the largest forward difference at the end of the previous step, or the difference between the current integer and the minimum integer to its left:

(define (largest-forward-difference xs)
  (let loop ((min-to-left (min (car xs) (cadr xs)))
             (max-so-far (- (cadr xs) (car xs)))
             (xs (cddr xs)))
    (if (null? xs) max-so-far
      (let* ((min-to-left (min min-to-left (car xs)))
             (diff-ending-here (- (car xs) min-to-left)))
        (loop min-to-left (max max-so-far diff-ending-here) (cdr xs))))))

This takes O(n) time and O(1) space. Here are some examples:

> (largest-forward-difference '(1 5 7 2 9))
8
> (largest-forward-difference '(4 3 2 1))
0

You can run the program at http://programmingpraxis.codepad.org/qOdxb2Yu.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
13 Comments »

13 Responses to “Largest Forward Difference”

  1. Francesco said
    January 20, 2015 at 12:31 PM

    Haskell:

    fd (i:[]) = 0
fd (i:is) = max (maximum $ map (subtract i) is) (fd is)
  2. klettier said
    January 20, 2015 at 5:04 PM 
    var ar = new[] { 1,5,7,2,9  };
int largestForwardDiff = 0;

for (int i = ar.Length - 1; i >= 1; i--)
{
    for (int ii = 0; ii < i; ii++)
    {
        var forwardDiff = ar[i] - ar[ii];

        if (forwardDiff > largestForwardDiff)
        {
            largestForwardDiff = forwardDiff;
        }
    }
}
  3. Mike said
    January 20, 2015 at 6:35 PM

    O(n) solution in Python

    def max_forward_diff(seq):
    max_diff = 0
    min_n = None
    
    for n in seq:
        if min_n is None or n < min_n:
            min_n = n
        max_diff = max(max_diff, n - min_n)
        
    return max_diff

    Or as a one-liner:

    import itertools as it
import operator as op

def max_fwd_diff(seq):
    return max(map(op.sub, seq, it.accumulate(seq, min)))
  4. inoakoala said
    January 20, 2015 at 10:24 PM

    I see that there are O(n^2) solutions.

    Is a O(n) solution possible?

    1. in array A find the maximum value x at position i.
    2. find the minimum value y at position j where 0 <= j <= i.
    3. largest forward difference is then max(x – y, 0).

  5. programmingpraxis said
    January 20, 2015 at 10:27 PM

    That doesn’t work. Consider the array (9,1,8). The largest forward difference is 8 – 1 = 7, but you will find the maximum value 9, find nothing to the left of it, and report a largest forward difference of 0.

  6. Axio said
    January 22, 2015 at 2:15 AM 
    ;; O(n) solution
(defun l-f-d (arr)
  (loop for i below (length arr)
        with mins = (make-array (length arr) :initial-element (aref arr 0))
        with maxs = (make-array (length arr) :initial-element (aref arr (1- (length arr))))
        when (> i 0)
        do
        (setf (aref mins i) (min (aref arr i) (aref mins (1- i))))
        when (< i (1- (length arr)))
        do
        (setf (aref maxs i) (max (aref arr i) (aref maxs (1+ i))))
        finally (return (max 0 (loop for i below (length arr) maximize
                                     (- (aref maxs i) (aref mins i)))))))
  7. klettier said
    January 22, 2015 at 9:12 AM

    Another solution in C# more powerful than the brut force one:

    int largestForwardDiff = 0;

int right = ar[ar.Length - 1];
int left = ar[0];
int currentDiff = right - left;

int tempRight = 0;

for (int i = ar.Length - 2; i >= 0; i--)
{
    if (ar[i] > right && ar[i] > tempRight)
    {
      tempRight = ar[i];
    }
    else if (ar[i] < left || (tempRight - ar[i] > currentDiff))
    {
        left = ar[i];

        if (tempRight != 0)
        {
            right = tempRight;

            tempRight = 0;
        }

        currentDiff = right - left;
    }
}

if (right > left)
{
    largestForwardDiff = right - left;
}
  8. matthew said
    January 22, 2015 at 9:41 AM

    Here’s a nice compact C++ solution, assumes at least 1 element, don’t think arithmetic overflow is a problem:

    #include <algorithm>
int maxfd(int *a, int len)
{
   int min = a[0], fd = 0;
   for (int i = 1; i < len; i++) {
      if (a[i] < min) min = a[i];
      else fd = std::max(fd, a[i]-min);
   }
   return fd;
}
  9. Brett Warren said
    January 22, 2015 at 9:49 AM

    A simple brute-force solution with some minor optimizations, namely going from the rightmost element comparing that with the numbers to its left, and than going from the second right-most element etc. until you reach the left-most element, avoiding duplicate comparisons.

    from itertools import islice

def max_forward_diff(num_set):
	diffs = list()
	
	for i, n in list(enumerate(num_set))[::-1]:
		for m in num_set[:i][::-1]:
			diffs.append(n-m)
			if n-m == max(num_set)-1 and n-m > 0:
				return n - m
	
	return max(diffs) if max(diffs) > 0 else 0

if __name__ == "__main__":
	print(max_forward_diff([1,3,2,4]))
  11. Mike said
    January 28, 2015 at 7:51 PM

    O(n) version in Haskell:

    mfd xs = maximum . zipWith (-) xs $ scanl1 min xs
  12. Mohamed Rafiqdeen said
    February 5, 2015 at 1:17 PM

    Simple Solution is: [1,5,7,2,9].inject {|a,b| (a-b).abs } = 8
    [4, 3, 2, 1].inject {|a,b| (a-b).abs } = 0

  13. Richard A. O'Keefe said
    June 1, 2015 at 7:12 AM

    max(x-cummin(x)) in R, I think.

Leave a comment