Как найти самую продолжительную последовательность, которая может быть либо убывающей либо нарастающей
Есть список
[1, 2, 3, 10, 8, 12, 13, 14]
Надо найти самую продолжительную последовательность. Например, для примера выше это
[1, 2, 3, 10]
А для такого списка [12, 11, 10, 8, 7, 1, 2, 3] решением будет
[12, 11, 10, 8, 7, 1]
На leetcode я нашёл решение только в одну сторону - либо нарастающая, либо убывающая последовательность. Решение типа - найти сперва для нарастающей, потом для убывающей последовательности, а потом сравнивать где больше элементов считаю неоптимальным. Подскажите плиз алгоритм решения
Ответы (1 шт):
Автор решения: turkindv
→ Ссылка
# lst = [12, 11, 10, 8, 7, 1, 2, 3]
lst = [1, 2, 3, 10, 8, 12, 13, 14]
last = lst[0]
lst_lt = [last]
lst_gt = [last]
mx_lt = []
mx_gt = []
for i in range(1, len(lst)):
if lst[i] > last:
lst_gt.append(lst[i])
mx_gt = max(mx_gt, lst_gt, key=len)
else:
lst_gt = [lst[i]]
if lst[i] < last:
lst_lt.append(lst[i])
mx_lt = max(mx_lt, lst_lt, key=len)
else:
lst_lt = [lst[i]]
last = lst[i]
result = mx_lt if len(mx_lt) > len(mx_gt) else mx_gt
print(result)