greedy - 使用贪心算法找到 ZIG-ZAG 序列

Question

整数序列 X=x1,x2...,xn 定义为 ZIG-ZAG 如果：

xi < xi+1 如果 xi 是奇数
xi > xi+1 如果 xi 是偶数

我需要一个贪心算法来找到给定序列内最大 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

只需遍历序列并检查每个元素是否满足条件。

你能试着解释一下贪心算法与此有什么关系吗？

编辑：好的，现在它比原版更有意义。不幸的是，我想不出一个好的解决方案 atm。