0
$\begingroup$

I have to create an algorithm for homework, but cant figure out where to start.

The divide and conquer algorithm muse be O(nlgn) and returns a pair of numbers p and q in an array A. p must appear before q in the array, and q-p must be the highest possible value

heres and example I made up:

A=[1,4,12,5,9,1,3,8]

the return values would be p=1 & q=12

$\endgroup$
  • $\begingroup$ I must be an idiot. Kept on thinking and wondering what is q-p. If anyone is still looking then it's difference of q,p. Simply put, OP is looking for pair numbers in the array which has highest difference. Here 12-1 giving 11. Next highest difference would be 12-3 = 9. $\endgroup$ – avi Sep 29 '13 at 12:35
  • 1
    $\begingroup$ @avi There's also the restriction that $p$ must appear before $q$ in the array so the next-highest acceptable difference is not $12-3=9$ but $12-4=9-1=8$. $\endgroup$ – David Richerby Sep 29 '13 at 15:34
  • $\begingroup$ oh, you are right. I did mistake again. $\endgroup$ – avi Sep 29 '13 at 15:39
4
$\begingroup$

Hint: Divide $A$ evenly into two smaller arrays $A_1,A_2$, and solve the problem (recursively) on $A_1$ and $A_2$. Can that help you find the optimum on $A$? Don't forget you're allowed to use extra processing costing up to $O(n)$.

Another hint: Suppose that $p,q$ is the optimal pair for $A$. Either $p,q \in A_1$, or $p,q \in A_2$, or neither of these cases is true. What can you say in the third case about $p$ and $q$?


As an aside, this can be solved in $O(n)$, in fact even online. We maintain the minimal element seen so far $m$, and the maximum difference $D = q-p$ over elements seen so far. Upon getting a new element $x$, we put $D = \max(D,x-m)$ and $m = \min(x,m)$, and update $p,q$ with $m,x$ if needed.

$\endgroup$
  • $\begingroup$ thanks :) (and good catch there), i had not read the question carefully, and thus leading to a trivial mistake.. i removed the answer (no point in having a wrong answer).. thanks again :) $\endgroup$ – Subhayan Sep 29 '13 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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