## 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.

Haskell:

O(n) solution in Python

Or as a one-liner:

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).

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.

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

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

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.

In Rust: http://xojoc.pw/programming-praxis/lfd.html

O(n) version in Haskell:

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

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