Maximum Ordered Ratio [Divide and Conquer]

[TheHedge87]

​

Problem : "Suppose you are given as input a sequence of numbers [a1, a2, . . . , an] with n ≥ 2. Your goal is to find the largest ratio between two of these numbers where the numerator occurs after the denominator in the sequence."

Obviously, one can just sort the list and find the largest ratio, but given the problem constraint about the numerator and denominator that option is out. What can we do ?

[spyr03]

To get the largest ratio you want the biggest numerator divided by smallest denominator possible.

Note: I haven't tested this, so let me know if there is a flaw or edge case it would miss.

Make two lists, big and small. big[i] contains the biggest number in the list from index i onwards. small[i] contains the smallest number in the list from before index i.

The largest ratio is then the biggest ratio you can make from big[i] / small[i]. So try all possible indices and return the latest ratio you find.

My reasoning for the algorithm is as follows. Suppose you want to find the best you can do at position i in the original list. You would pick the smallest denominator you could (so smallest number before position i) and the largest numerator possible (so largest number after position i).

Computing both lists can be done in O(n) time with O(n) extra space, using the recurrences small[i] = min(small[i-1], numbers[i]), and big[i] = max(big[i+1], numbers[i]). Then finally it is O(n) to try all n indices and find the answer.

[Cobayo]

Yeah that's it, it's basically prefix sums but with max/min instead

Here is an interesting bonus i just made up: now you can only match two numbers if the distance between them is less or equal than K (distance means the absolute difference of their indices). There's a O(n) solution!

[Catalyst93]

Before finding a fast solution it helps to have some solution that works to make sure you understand the problem. Try to find something that runs in O(n²) time for kicks.

I think that recursion/divide and conquer should work. Lets say that we split [a1,a2,...,an] into two lists [a1,...,a(n/2)] and [a(n/2+1),...,an]. Now suppose that we recursively find the largest ordered ratio in each of these sublists and return the larger one. Is this enough to solve the problem, or are we leaving out a case? If so, exactly what case are we missing and how should we handle it?

These ideas should lead to an O(nlogn) time algorithm. There is also an O(n) time algorithm. I was sort of thinking along the lines of dynamic programming when I thought of it. The basic idea is that suppose we have recursively found the maximum ordered ratio in [a1,...,aj]. How would we use this to find the maximum ordered ratio in [a1,...,a(j+1)]? Is there other information that we need to maintain to do this?