Волнистая последовательность Опции

[xprogrammer]

Назовенм последовательность волнистой если для всех кроме первого элемента выполняется: для всех элементов кроме первого и последнего, что либо этот член последовательности больше всех своих соседей, либо меньше.
Например : 12121212121-волнистая
а 123321 - нет
дана последовательность и надо из неё выделить самую большую волнистую подпоследовательность .
Последовательность храниться в массиве помогите хоть алгоритмом.

[xprogrammer]

нет, вы неправильно мепня поняяли. Подпоследовательностью последовательности (Xn) я имею ввиду любой упорядоченный набор элементов последовательности (yn) где если Yi , yj ( элементы последовательности) и I>j то номер элемента Yi в последовательности Xn будет больше номера Yj в последовательности Xn
Например:
Xn : 1 2 3 4 5 6 7 8 9 0
Yn : 1 3 5 7 9

[Michael_Rybak]

Подпоследовательностью последовательности (Xn) я имею ввиду любой упорядоченный набор элементов последовательности (yn) где если Yi , yj ( элементы последовательности) и I>j то номер элемента Yi в последовательности Xn будет больше номера Yj в последовательности Xn

О, вот это уже поинтереснее

Считаем, что в массиве все числа - от 0 до n-1. Если это не так, то понятно, что можно построить биекцию.

Введем понятие верхних и нижних волнистых подпоследовательностей. Верхней называем такую, у которой последнее число *больше* предпоследнего, нижней - такую, у которой последнее число *меньше* предпоследнего. Подпоследовательности длины 0 и 1 являются и верхними, и нижними одновременно.

Заведем два массива: А[0 .. n-1] и В[0 .. n-1]. Изначально A[i] = B[i] = 0 для всех i.

Идем слева направо по входному массиву (напомню, что все числа в нем - от 0 до n-1). После прочтения каждого числа состояние массивов А и В должно быть таким: A[i] - длина максимальной волнистой верхней подпоследовательности в прочитанном куске, оканчивающейся числом i, B[i] - длина максимальной волнистой нижней подпоследовательности в прочитанном куске, оканчивающейся числом i.

В начале все A[i] = B[i] = 0, потому что еще ничего не прочитано. Теперь, пусть мы прочли число x. В результате могут поменяться только значения A[x] и B[x]. Они станут равны:

A[x] = max(B[0], B[1], B[2], .., B[x-1]) + 1

B[x] = max(A[x+1], A[x+2], A[x+3], .. , A[n - 1]) + 1

Действительно, чтобы с помощью х получить наилучшую верхнюю подпоследовательность, нужно приписать х к наилучшей из найденных нижних подпоследовательностей, оканчивающихся числами, меньшими х. И наоборот.

Пройдя слева направо по всему входному массиву, мы заполним постепенно массивы А и В. Теперь наибольшему из всех чисел в А и В соответствует самая длинная волнистая подпоследовательность. Как ее теперь построить - додумаешь сам.

Вот. Это решение очень легко пишется, и работает за квадрат. Если тебе надо за n log n, разберись с этим, и приходи