5
$\begingroup$

I don't know an O(n) solution to the following:

Given an array of n integers, find the largest difference between any two pairs in the array: however, the larger integer must have a higher index in the array than the other.

Ex: alg({9, 2, 6, 7}) = 5

It seems straightforward, yet it eludes me.

$\endgroup$
  • $\begingroup$ This is a dump of a problem, not a question. If you have a specific question regarding the wording of the problem or about concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See also here for our homework policy, and here for a relevant discussion. You may also want to check out our reference questions; your problem may be covered there. $\endgroup$ – Raphael Jan 29 '14 at 17:01
5
$\begingroup$

Create an array considering the minimum value seen so far in the array (in O(n)).

Ex. (9, 2, 2, 2)

Create an array containing the differences between the previous array and the original array (again, in O(n)).

Ex. (0, 0, 4, 5)

Find the maximum value in the array (O(n)). In this case, the answer is 5 as required.

This can be done in O(1) memory and only one pass if a few optimizations are made.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Why mention creating the array at all? It wastes memory and complicates the description. $\endgroup$ – David Richerby Jan 29 '14 at 10:01
-1
$\begingroup$

It is rather tempting to think that the problem asks for the largest and smallest integers in the array such that the larger integer has a higher index, and therefore forget about "largest difference". It is rather straightforward if you don't get trapped in thoughts like that! The code below solves the problem:

larger = array[1];
smaller = array[0];
smallest = array[0];
largest_difference = array[1]-array[0];

for(i=1; i<n-1; i++)
{
    if(array[i] < smallest)
        smallest = array[i];

    if( array[i+1] - smallest > largest_difference )
    {
        largest_difference = array[i+1] - smallest;
        smaller = smallest;
        larger = array[i+1];
    }
}

Proof: In short, for every integer X in the array starting from X=array[1], we know the smallest integer S before it. We compute its difference with this smallest integer (X-S), and so we know the largest difference as far as 'X' is concerned. As we do this for all X, we keep track of the largest of these 'largest differences'.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This code cannot be correct. The variable smaller is assigned to but never read; the variable largest_difference is never updated. $\endgroup$ – David Richerby Jan 29 '14 at 14:09
  • $\begingroup$ Thanks, I forgot to add the line to update largest_difference. But the proof does say we keep track of it. The variable smaller does not need to be read. I assumed it was required by the problem statement. $\endgroup$ – yemelitc Jan 29 '14 at 14:32

Not the answer you're looking for? Browse other questions tagged or ask your own question.