最大有序比[分治算法]

Question

问题："假设输入一个n≥2的数字序列[a1，a2，…，an]。你的目标是找到这两个数字之间的最大比率，其中分子出现在序列中的分母之后。">

显然，人们可以对列表进行排序，找到最大的比率，但考虑到分子和分母的问题约束，这个选项就不存在了。我们能做什么？因此，由于索引很重要，所以数组的排序基本上是多余的。

Answer 1

您不必对元素数组进行排序。您可以从数组的末尾到数组的开头进行检查。请参阅下面的算法：

n = size of array  A // array are 0 indexed
numerator = A[n-1]
denominator = A[n-2]
max_numerator = max(A[n-1], A[n-2])
for i = n-3 to 0 {
// assume A[i] as denominator
if (numerator/denominator) < (max_numerator/A[i]) {
numerator = max_numerator
denominator = A[i]
}
max_numerator = max(max_numerator, A[i])
}