元素的值先减小后增大的序列称为V-Sequence。在一个有效的 V 序列中，应该至少有一个元素在递减臂中，并且至少有一个元素在递增臂中。
例如，“5 3 1 9 17 23”是一个有效的 V 序列，在递减臂中有两个元素，即 5 和 3，在递增臂中有 3 个元素，即 9、17 和 23。但是序列“6 4 2”或“8 10 15”都不是 V 序列，因为“6 4 2”在递增部分没有元素，而“8 10 15”在递减部分没有元素。
给定一个包含 N 个数字的序列，找到它最长的(不一定是连续的)子序列，即 V 序列？
是否可以在 O(n)/O(logn)/O(n^2) 中执行此操作？
最佳答案
该解与最长非递减子序列的解非常相似。不同之处在于，现在对于每个元素，您需要存储两个值——从该元素开始的最长 V 序列的长度是多少，以及从该元素开始的最长递减子序列的长度是多少。请看一下typical non-decreasing subsequence的解决方案解决方案，我相信这应该是一个足够好的提示。我相信您可以实现的最佳复杂度是 O(n*log(n))，但是复杂度为 O(n^2) 的解决方案更容易实现。
希望这对您有所帮助。
关于algorithm - 递增递减序列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9783943/