最長交替序列

Question

的序列X1，X2，X3，...，XN，是鋸齒形如果

如果X = 3, 4, 8, 5, 6, 2然後最長鋸齒形子序列的長度是5（對應到3, 8, 5, 6, 2或4, 8, 5, 6, 2）。

我們將Z（i，0）定義爲以xi結束的最長鋸齒形子序列的偶數長度。我們將Z（i，1）定義爲最長鋸齒形子序列的ODD長度，並以xi結束。

這裏是解決復發：

現在我的問題是，如果有另一種方式來構建具有唯一參數i變量Z，並納入0 and 1函數內部的復發。 如果我們將Z[i]定義爲以xi結束的最長的zig-zag子序列（奇數或偶數）的長度，那麼如果z [i]是奇數或偶數，我們如何表示信息？ 那會再發生什麼？

編輯：我在復發上工作了一點，我想出了這個解決方案。我認爲這是正確的。別人能確認嗎？ 讓我們定義c [i]是xi前綴Xi的最長鋸齒子序列（奇數或偶數）。如果我們在序列中只有一個元素，那麼c [1] = 1 要計算i> 1的c [i]，首先我們計算（i-1）元素（奇數和偶數）的最長鋸齒子序列。我們選擇兩者中的最大值並加1.我們使用c[j] mod 2 == 0控件來選擇只有偶數的長度。

2 http://imageshack.com/a/img537/402/egyXmk.jpg

Answer 1

這是不可能的。無論後續序列的長度是偶數還是奇數都是信息的重要組成部分，否則公式將不起作用。它不能從i派生。