# create divide and conquer algorithm

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

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

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.