Максимальное упорядоченное отношение [Алгоритмы «разделяй и властвуй»]

Question

Проблема: «Предположим, что в качестве входных данных вам дана последовательность чисел [a1, a2, ..., an] с n ≥ 2. Ваша цель - найти наибольшее соотношение между двумя из этих чисел, где числитель встречается после знаменатель в последовательности. "

Очевидно, что можно просто отсортировать список и найти наибольшее соотношение, но, учитывая ограничение задачи о числителе и знаменателе, эта опция отсутствует. Что мы можем сделать? Так как индексация важна, сортировка массива в значительной степени завершена.

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])
}