Maximum Ordered Ratio [Divide and Conquer]

3677 views algorithm

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 ?

answered question

1 Answer


You can place a condition of checking that index of numerator is greater than the denominator, before calculating a ratio.

posted this

Have an answer?


Please login first before posting an answer.