元素的值先减少然后增加的序列称为V序列。在有效的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/