Задача с собеседования в Яндекс

Дан массив чисел a₁, a₂, ..., aₙ.
Необходимо найти строго монотонный подотрезок (то есть строго убывающий или строго возрастающий) максимальной длины и вернуть пару индексов его начала и конца.

Решение:
Решение за линейное время и константную память (изменять входной массив нельзя).
В идеале: решить за один проход, отслеживая текущую монотонную последовательность, её направление и корректно сбрасывая при изменении направления и аккуратно обновляя максимум при переходе к следующему числу.

Также допустим подход в два прохода: отдельно ищем максимум среди возрастающих и убывающих отрезков. Но это менее оптимально, и большинство кандидатов ошибаются, пытаясь объединить оба направления в одном проходе.

def find_longest_monotonic_subarray(arr):
if not arr:
return (0, 0)

max_start = max_end = 0
cur_start = 0
direction = 0 # 1 — возрастаем, -1 — убываем, 0 — нет направления

for i in range(1, len(arr)):
if arr[i] > arr[i - 1]:
if direction == -1:
cur_start = i - 1
direction = 1
elif arr[i] < arr[i - 1]:
if direction == 1:
cur_start = i - 1
direction = -1
else:
direction = 0
cur_start = i
continue

if (i - cur_start) > (max_end - max_start):
max_start, max_end = cur_start, i

return (max_start, max_end)

@algoses