Largest Forward Difference

January 20, 2015

In an array of integers, the forward difference between any two elements is the rightmost integer less the leftmost integer. The largest forward difference is the greatest value of all forward differences between elements of the array. If there are no positive forward differences, the largest forward difference is taken to be zero, as if an integer is subtracted from itself.

For instance, in the array [1,5,7,2,9] the largest forward difference is 9 – 1 = 8, and in the array [4, 3, 2, 1] the largest forward difference is 0.

Your task is to write a program that finds the largest forward difference in an array. 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.

Pages: 1 2

13 Responses to “Largest Forward Difference”

  1. Francesco said

    Haskell:

    fd (i:[]) = 0
    fd (i:is) = max (maximum $ map (subtract i) is) (fd is)
    
  2. klettier said
    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

    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

    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

    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
    ;; 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

    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

    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

    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]))
    
  10. Mike said

    O(n) version in Haskell:

    mfd xs = maximum . zipWith (-) xs $ scanl1 min xs
    
  11. Mohamed Rafiqdeen said

    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

  12. Richard A. O'Keefe said

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

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

%d bloggers like this: