Найти последовательность зигзагообразной с жадным алгоритмом

Question

Целого последовательность Х = x1, x2, ..., хп определяются зигзагообразным, если:

< х Xi + 1, если х являются нечетным число
XI> xi + 1, если х четное число

мне нужен жадный алгоритм, чтобы найти измерение максимальной ZIG-ZAG подпоследовательности внутри данной последовательности

EDIT: Там пример:
Y = (3, 4, 8, 5, 6, 2)
Выход должен быть 5 для 3, 8, 5, 6, 2 или 4, 8, 5, 6, 2

Answer 1

Вы могли бы попытаться объяснить, что такое greedy algorithms?

Редактировать: ok, теперь это имеет больше смысла, чем в оригинале. К сожалению, я не могу придумать хорошее решение atm.

Answer 2

вы можете использовать этот алгоритм (только инициализацию о (дд) и е (вэн) массивы 1):

for i=1 to n 
for j=i-1 down to 1 do 
if a[i]>a[j] and o[i]< e[j]+1 then o[i]=e[j]+1 
else if a[i]<a[j] and e[i]<o[j]+1 then e[i]=o[j]+1 

Ответ максимум уплотнительными и электронных массивов.