create divide and conquer algorithm

Question

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

• avi: 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.
• David Richerby: @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$.
• avi: oh, you are right. I did mistake again.

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.

• Subhayan: 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 :)