What is the fastest way to find a subsequence of a given sequence that every element before is less and every element after is greater

user_3149564 0
Viewed 136

What is the fastest way to find a subsequence of a given sequence under the condition that for each element x in the subsequence, every element in the given sequence before x is less than x and every element in the given sequence after x is greater than x?

Sample input

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

Sample output

20, 25, 30
subsequence algorithm
1 Answers

Start with your sequence and construct maximums to the left, minimums to the right:

  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

Pull out the ones where the three arrays match. In this case 20, 25, 30.

This takes time and memory O(n).

user_5854110
Related