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
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).