最長的zig-zag子序列使用動態編程

我需要編寫一個method that needs to return the length of the longest subsequence of sequence that is a zig-zag sequence.算法的方法應該是動態編程。最長的zig-zag子序列使用動態編程

數字序列被稱爲zig-zag sequence如果連續數字正與負之間交替的嚴格之間的差異。第一個差異（如果存在的話）可能是正面的或負面的。

Eg - 1,7,4,9,2,5 is a zig-zag sequence 
because the differences (6,-3,5,-7,3) are alternately positive and negative. 

1,4,7,2,5 is not a zig-zag sequence.

我的代碼：

public static int longestZigZag(int[] seq){ 

    int len = seq.length; 
    int[] count= new int[len]; 

    for(int i=0;i<len;i++) 
     count[i]=1; 

    for(int i=1;i<len;i++){ 
     int k = (int)Math.pow(-1, i+1); 

     if(seq[i]>(k*seq[i-1])){ 
      count[i]=count[i-1]+1; 
     } 
    } 

    int max=1; 
    for(int i=0;i<len;i++) 
     if(count[i]>max) 
      max=count[i]; 

    return max; 
}

說明：

對應每埃爾另外，我有一個count元素，表示到那時爲止的連續替代序列。

seq: 1, 7, 4, 9, 2, 5 
count: 1, 1, 1, 1, 1, 1 

i=1 7 > 1 count[1]= count[0]+1 = 2 
i=2 4 > -7 count[2]= count[1]+1 = 3 
i=1 9 > 4 count[3]= count[2]+1 = 4 
i=1 2 > -9 count[4]= count[3]+1 = 5 
i=1 5 > 2 count[5]= count[4]+1 = 6

之後，我只是打印計數數組的最大值。

錯誤：

上述工作正確的

{ 1, 7, 4, 9, 2, 5 }      -> 6 
{ 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 } -> 7

但是，它給出了

{ 1, 2, 3, 4, 5, 6, 7, 8, 9 } gives 9 but should be 2. 
{ 70, 55, 13, 2, 99, 2, 80, 80, 80, 80, 100, 19, 7, 5, 
    5, 5, 1000, 32, 32 } gives 2 but should be 8.

來源

2012-11-16 OneMoreError

我不知道怎麼回答的，這是錯誤的結果。。。你的方法是完全錯誤的。： -/

看到這一點，考慮以下幾點：您計算的count每個元素只依賴的count單前一個元素上，和你的跑步計算max只依賴的count當前元素上。這意味着您甚至不需要count數組：您的整個算法可以轉換爲需要O（1）空間的單個通道。但是，作爲一個「測試者」，你知道這個問題不能用012空間解決（容易），因爲如果它是可能是，你不會被指示使用動態編程。

算法錯誤的核心原因是您只將seq的每個元素與它的前一個元素進行比較，但子序列被允許（通常是）「跳過」中間值。

一個混淆的因素，這是你的輸出的一些更令人困惑的方面負責，是seq[i]>(k*seq[i-1])檢查並不意味着我認爲你的想法意味着什麼。你可能想要更接近k*(seq[i]-seq[i-1])>0 —，但即使這樣也會給出相當錯誤的結果。你真的只需要放棄這個算法並寫一個新的算法。

來源

2012-11-16 16:39:13 ruakh

最長的zig-zag子序列使用動態編程

回答

相關問題