Нахождение самого длинного строго монотонного подпоследовательного отрезка в массиве

Условие

Дан массив чисел. Нужно определить максимальный по количеству элементов непрерывный отрезок, где элементы образуют строго возрастающую либо строго убывающую последовательность, и вернуть пару индексов её начала и конца. Примеры: [2, 7, 5, 4, 4, 3] -> {1, 3} [1, 1] -> {1, 1} // или {0, 0}

Ответ

Поддерживайте начала текущих строго возрастающего и убывающего отрезков. Равные соседние элементы обрывают оба; после каждого шага обновляйте лучший диапазон.

def longest_monotonic(arr):
    if not arr:
        return None
    inc = dec = 0
    best = (0, 0)
    for i in range(1, len(arr)):
        if arr[i] <= arr[i - 1]:
            inc = i
        if arr[i] >= arr[i - 1]:
            dec = i
        start = min(inc, dec)
        if i - start > best[1] - best[0]:
            best = (start, i)
    return best

Индексы с нуля, границы включены. Для первого примера получится (1, 3), для [1, 1] — (0, 0). При равной длине сохраняется первый найденный диапазон. Время O(n), память O(1).