Как решить задачу линейным алгоритмом? Задачу решить могу, но вообще не выкупаю, почему в первом тесте ответ 2 5, а не 1 4: Отношение Дан массив a1,a2,...an. Необходимо выбрать в нём два элемента ai и aj, такие что i < j, и отношение aj/ai — максимально и больше 1. Входные данные В первой строке задано целое число 2 ⩽n⩽ 100 000 — количество элементов в массиве. Во второй строке заданы n целых положительных чисел ai(1 ⩽i⩽n, 1 ⩽ai⩽ 5000). Выходные данные Выведите два числа — индексы элементов i и j. Если ответов несколько, то выведите любой из них. Если ответа нет, то выведите два нуля, разделённых пробелом.Тесты 6 10 3 5 3 11 92 5 4 5 5 5 50 0

Предыдущий
вопрос Следующий
вопрос

Для решения этой задачи линейным алгоритмом можно использовать следующий подход:

Создать переменные для хранения индексов элементов i и j.Создать переменные для хранения максимального отношения и минимального элемента.Проитерироваться по массиву от начала до конца.Если текущий элемент больше минимального элемента, но отношение между текущим элементом и минимальным больше максимального отношения, то обновить максимальное отношение и индексы i и j.Обновить минимальный элемент, если текущий элемент меньше.

Пример кода на Python:

n = int(input())
arr = list(map(int, input().split()))
max_ratio = 0
min_element = arr[0]
result_i = 0
result_j = 0
for i in range(1, n):
if arr[i] > min_element and arr[i] / min_element > max_ratio:
max_ratio = arr[i] / min_element
result_i = arr.index(min_element) + 1
result_j = i + 1
if arr[i] < min_element:
min_element = arr[i]
if max_ratio > 1:
print(result_i, result_j)
else:
print(0, 0)

Этот алгоритм проходит по массиву только один раз, что делает его линейным.