Последовательность, в которой значение элементов сначала уменьшается, а затем увеличивается, называется 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) ?