找到给定序列的子序列的最快方法是什么，该子序列之前的每个元素都较小，而之后的每个元素都较大

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

找到给定序列的子序列的最快方法是什么，该子序列之前的每个元素都较小，而之后的每个元素都较大

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

algorithm

subsequence