Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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
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.
