增加减少序列

Question

元素值首先减少然后增加的序列称为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)中执行此操作？

Answer 1

该解与最长非减子序列的解非常相似。不同之处在于，现在对于每个元素，您需要存储两个值 - 从该元素开始的最长 V 序列的长度是多少，以及从该元素开始的最长递减子序列的长度是多少。请看一下典型的非递减子序列解决方案的解决方案，我相信这应该是一个足够好的提示。我相信您可以实现的最佳复杂度是 O(n*log(n))，但复杂度为 O(n^2) 的解决方案更容易实现。

希望这可以帮助。