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:


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

  • $\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
    Commented Sep 29, 2013 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$ Commented Sep 29, 2013 at 15:34
  • $\begingroup$ oh, you are right. I did mistake again. $\endgroup$
    – avi
    Commented Sep 29, 2013 at 15:39

1 Answer 1


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.

  • $\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
    Commented Sep 29, 2013 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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