greedy - 欲張りアルゴリズムを使用してZIG-ZAGシーケンスを検索する

Question

整数列X=x1、x2 ...、xnは、次の場合にZIG-ZAGで定義されます。

xiが奇数の場合はxi<xi+1xiが偶数の場合は
xi>xi+ 1

与えられたシーケンス内の最大ZIG-ZAGサブシーケンスの次元を見つけるために欲張りアルゴリズムが必要です

編集：例があります：
Y =（3、4、8、5、6、2）
出力は3、8、5、6、2または4、8、5、6、2の場合は5である必要があります

Answer 1

このアルゴリズムを使用できます（o（dd）およびe（ven）配列を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

答えは、o 配列と e 配列の最大値です。

Answer 2

シーケンスを実行して、条件が満たされているかどうかを各要素で確認するだけです。

貪欲なアルゴリズムがこれにどのような関係があるのか​​説明していただけますか?

編集：わかりました、今ではオリジナルよりも理にかなっています。残念ながら、良い解決策が思いつきません。