Учитывая несортированный массив, найдите разницу max
j - i
между индексами, такую что j > i
и a[j] > a[i]
в O(n)
. Я могу найти j
и i
с помощью тривиальных методов в O(n^2)
сложности, но хотел бы знать, как это сделать в O(n)
?
Вход: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}
Выход: 8 (j = 8, я = 0)
Вход: {1, 2, 3, 4, 5, 6}
Выход: 5 (j = 5, я = 0)