[Solved]: create divide and conquer algorithm

Problem Detail: 

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

Asked By : Leshawn

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14665

3.2K people like this

 Download Related Notes/Documents