increasing decreasing sequence

Question

A sequence in which the value of elements first decrease and then increase is called V- Sequence. In a valid V-Sequence there should be at least one element in the decreasing and at least one element in the increasing arm.

For example, "5 3 1 9 17 23" is a valid V-Sequence having two elements in the decreasing arm namely 5 and 3, and 3 elements in the increasing arm namely 9, 17 and 23 . But none of the sequence "6 4 2" or "8 10 15" are V-Sequence since "6 4 2" has no element in the increasing part while "8 10 15" has no element in the decreasing part.

Given a sequence of N numbers find its longest (not necessarily contiguous) sub-sequence which is a V-Sequence ?

Is it possible to do this in O(n)/O(logn)/O(n^2) ?

Answer 1

The solution is quite similar to the solution of the longest-non-decreasing subsequence. The difference is that now for each element you need to store two values - what is the length of the longest V sequence starting from this element and what is the length of the longest decreasing subsequence starting at this. Please take a look at the solution of the typical non-decreasing subsequence solution and I believe this should be a good enough tip. I believe the best complexity you can achieve is O(n*log(n)), but a solution of complexity O(n^2) is easier to achieve.

Hope this helps.