Какой самый быстрый способ найти подпоследовательность данной последовательности, что каждый элемент до меньше, а каждый элемент больше

Question

Какой самый быстрый способ найти подпоследовательность данной последовательности при условии, что для каждого элемента x в подпоследовательности каждый элемент в данной последовательности до x меньше x и каждый элемент в данная последовательность после x больше x?

Пример ввода

9, 8, 7, 6, 5, 8, 9, 10, 11, 12, 10, 5, 2, 20, 25, 30, 80, 90, 100, 50, 40, 41

Пример вывода

20, 25, 30

Answer 1

Начните с вашей последовательности и постройте максимумы слева, минимумы справа:

  9,   8,   7,   6,   5,   8,   9,  10,  11,  12,  10,   5,   2,  20,  25,  30,  80,  90, 100,  50,  40,  41
  9,   9,   9,   9,   9,   9,   9,  10,  11,  12,  12,  12,  12,  20,  25,  30,  80,  90, 100, 100, 100, 100
  2,   2,   2,   2,   2,   2,   2,   2,   2,   2,   2,   2,   2,  20,  25,  30,  40,  40,  40,  40,  40,  41

Вытащите те, где совпадают три массива.В этом случае 20, 25, 30.

Это занимает время и память O(n).