算法 - 最長擺動子序列

Question

算法：

數字序列被稱爲蠕動序列如果差異 連續數字正和負 之間嚴格交替之間。第一個差異（如果存在的話）可能是正數 或負數。具有少於兩個元素的序列一般是擺動序列。

例如，[1,7,4,9,2,5]是一個擺動序列，因爲 差異（6，-3,5，-7,3）交替爲正數和負數。相比之下，[1,4,7,2,5]和[1,7,4,5,5]不是擺動序列， 首先是因爲它的前兩個差異是正的，而第二個是因爲其最後的差異是零。

給定一個整數序列，返回最長的 子序列的長度，這是一個擺動序列。通過 刪除 原始序列中的一些元素（最終也爲零），從而使其餘元素保持其原始 的順序，從而獲得子序列。

實例：

Input: [1,7,4,9,2,5] 
Output: 6 
The entire sequence is a wiggle sequence. 

Input: [1,17,5,10,13,15,10,5,16,8] 
Output: 7 
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8]. 

Input: [1,2,3,4,5,6,7,8,9] 
Output: 2 

我的溶液：

def wiggle_max_length(nums) 
    [ build_seq(nums, 0, 0, true, -1.0/0.0), 
     build_seq(nums, 0, 0, false, 1.0/0.0) 
    ].max 
end 

def build_seq(nums, index, len, wiggle_up, prev) 
    return len if index >= nums.length 
    if wiggle_up && nums[index] - prev > 0 || !wiggle_up && nums[index] - prev < 0 
     build_seq(nums, index + 1, len + 1, !wiggle_up, nums[index]) 
    else 
     build_seq(nums, index + 1, len, wiggle_up, prev) 
    end 
end 

這是工作於較小的輸入（例如[1,1,1,3,2,4,1,6， 3,10,8]和所有樣本輸入，但其失敗的非常大的輸入（這是很難調試），如：

[33,53,12,64,50,41,45 ，21,97,35,47,92,39,0,93,55,40,46,69,42,6,95,51,68,72,9,32,84,34,64,6,2 ，26,98,3,43,30,60,3,68,82,9,97,19,27,98,99,4,30,96,37,9,78,43,64,4,65 ，30,84,90,87,64,18,50,60,1,40,32,48,50,76,100,57,29,63,53,46,57,93,98,42,80,82 ，9,41,55,69,84,82,79,30,79,18,97,67,23,52,38,74,15]

其中應該有輸出：67但我soln輸出57.有人知道這裏有什麼問題嗎？

Answer 1

該方法嘗試的是一個貪婪的解決方案（因爲它總是使用當前元素，如果它滿足擺動條件），但這並不總是奏效。 我會嘗試用這個更簡單的反例來說明這一點：1 100 99 6 7 4 5 2 3。

一個最好的子序列爲：1 100 6 7 4 5 2 3，但是從算法兩個build_seq通話會產生這些序列：

• 1 100 99
• 1

---

編輯：稍微修改貪婪的方法確實有效 - 參見this link，感謝Peter de Rivaz。

Answer 2

設Wp [i]是從元素i開始的最長擺動序列，並且第一個差值爲正值。讓Wn [i]是相同的，但第一個區別是負的。

然後：

Wp[k] = max(1+Wn[k'] for k<k'<n, where A[k'] > A[k]) (or 1 if no such k' exists) 
Wn[k] = max(1+Wp[k'] for k<k'<n, where A[k'] < A[k]) (or 1 if no such k' exists) 

這給出了以僞代碼

Wp = [1, 1, ..., 1] -- length n 
Wn = [1, 1, ..., 1] -- length n 
for k = n-1, n-2, ..., 0 
    for k' = k+1, k+2, ..., n-1 
     if A[k'] > A[k] 
      Wp[k] = max(Wp[k], Wn[k']+1) 
     else if A[k'] < A[k] 
      Wn[k] = max(Wn[k], Wp[k']+1) 
result = max(max(Wp[i], Wn[i]) for i = 0, 1, ..., n-1) 

Answer 3

動態規劃可用於獲得最優解爲O（n^2）動態規劃溶液，在這裏。

注意：我在看到@PeterdeRivaz提到的​​之前寫了這個。雖然動態編程（O（n（））有效，但本文提出了一種優越的（O（n））「貪婪」算法（「方法5」），與動態編程解決方案相比，它更易於編碼。我添加了第二個實現該方法的答案。

代碼

def longest_wiggle(arr) 
    best = [{ pos_diff: { length: 0, prev_ndx: nil }, 
      neg_diff: { length: 0, prev_ndx: nil } }] 
    (1..arr.size-1).each do |i| 
    calc_best(arr, i, :pos_diff, best) 
    calc_best(arr, i, :neg_diff, best) 
    end 
    unpack_best(best) 
end 

def calc_best(arr, i, diff, best) 
    curr = arr[i] 
    prev_indices = (0..i-1).select { |j| 
    (diff==:pos_diff) ? (arr[j] < curr) : (arr[j] > curr) } 
    best[i] = {} if best.size == i 
    best[i][diff] = 
    if prev_indices.empty? 
     { length: 0, prev_ndx: nil } 
    else 
     prev_diff = previous_diff(diff) 
     j = prev_indices.max_by { |j| best[j][prev_diff][:length] } 
     { length: (1 + best[j][prev_diff][:length]), prev_ndx: j } 
    end 
end 

def previous_diff(diff) 
    diff==:pos_diff ? :neg_diff : :pos_diff· 
end 

def unpack_best(best) 
    last_idx, last_diff = 
    best.size.times.to_a.product([:pos_diff, :neg_diff]). 
     max_by { |i,diff| best[i][diff][:length] } 
    return [0, []] if best[last_idx][last_diff][:length].zero? 
    best_path = [] 
    loop do 
    best_path.unshift(last_idx) 
    prev_index = best[last_idx][last_diff][:prev_ndx] 
    break if prev_index.nil? 
    last_idx = prev_index· 
    last_diff = previous_diff(last_diff) 
    end 
    best_path 
end 

實例

longest_wiggle([1, 4, 2, 6, 8, 3, 2, 5]) 
    #=> [0, 1, 2, 3, 5, 7]] 

最長擺動的長度爲6，並在索引由元素,1,2,3,5和7，即[1, 4, 2, 6, 3, 5]。

第二個示例使用問題中給出的較大數組。

arr = [33, 53, 12, 64, 50, 41, 45, 21, 97, 35, 47, 92, 39, 0, 93, 55, 40, 46, 
     69, 42, 6, 95, 51, 68, 72, 9, 32, 84, 34, 64, 6, 2, 26, 98, 3, 43, 30, 
     60, 3, 68, 82, 9, 97, 19, 27, 98, 99, 4, 30, 96, 37, 9, 78, 43, 64, 4, 
     65, 30, 84, 90, 87, 64, 18, 50, 60, 1, 40, 32, 48, 50, 76, 100, 57, 29, 
arr.size   63, 53, 46, 57, 93, 98, 42, 80, 82, 9, 41, 55, 69, 84, 82, 79, 30, 79, 
     18, 97, 67, 23, 52, 38, 74, 15] 
    #=> 100 
longest_wiggle(arr).size 
    #=> 67 
longest_wiggle(arr) 
    #=> [0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 12, 14, 16, 17, 19, 21, 22, 23, 25, 
    # 27, 28, 29, 30, 32, 34, 35, 36, 37, 38, 39, 41, 42, 43, 44, 47, 49, 50, 
    # 52, 53, 54, 55, 56, 57, 58, 62, 63, 65, 66, 67, 70, 72, 74, 75, 77, 80, 
    # 81, 83, 84, 90, 91, 92, 93, 95, 96, 97, 98, 99] 

如上所述，最大的擺動由arr的67個元素組成。解決時間基本上是瞬時的。

這些指數的arr的值如下。

[33, 53, 12, 64, 41, 45, 21, 97, 35, 47, 39, 93, 40, 46, 42, 95, 51, 68, 9, 
84, 34, 64, 6, 26, 3, 43, 30, 60, 3, 68, 9, 97, 19, 27, 4, 96, 37, 78, 43, 
64, 4, 65, 30, 84, 18, 50, 1, 40, 32, 76, 57, 63, 53, 57, 42, 80, 9, 41, 30, 
79, 18, 97, 23, 52, 38, 74, 15] 

[33, 53, 12, 64, 41, 45, 21, 97, 35, 92, 0, 93, 40, 69, 6, 95, 51, 72, 9, 84, 34, 64, 2, 98, 3, 43, 30, 60, 3, 82, 9, 97, 19, 99, 4, 96, 9, 78, 43, 64, 4, 65, 30, 90, 18, 60, 1, 40, 32, 100, 29, 63, 46, 98, 42, 82, 9, 84, 30, 79, 18, 97, 23, 52, 38, 74] 

說明

我本來打算提供的算法及其實現的解釋，但自從學會有一個優越的方法有（見我記在我的答案的開始），我已決定不這樣做，但當然會很樂意回答任何問題。除此之外，我的筆記中的鏈接解釋瞭如何使用動態編程。

Answer 4

在對@ quertyman的回答發表評論時，@PeterdeRivaz提供了一個指向​​的鏈接，該鏈接考慮瞭解決「最長擺動子序列」問題的各種方法。我實施了「方法＃5」，其具有O（n）的時間複雜性。

該算法既簡單又快速。第一步是從每對相等的連續元素中移除一個元素，並繼續這樣做直到沒有連續的元素相等爲止。例如，[1,2,2,2,3,4,4]將被轉換爲[1,2,3,4]。最長的擺動子序列包括結果數組的第一個和最後一個元素，a，以及每個元素a[i],0 < i < a.size-1，其中a[i-1] <a[i]> a[i+1]或a[i-1] > a[i] > a[i+1]。換句話說，它包括第一個和最後一個元素以及所有的峯和谷底。在下面的圖表中，這些元素是A，D，E，G，H，I（從上面引用的文章中獲得，獲得許可）。

代碼

def longest_wiggle(arr) 
    arr.each_cons(2). 
     reject { |a,b| a==b }. 
     map(&:first). 
     push(arr.last). 
     each_cons(3). 
     select { |triple| [triple.min, triple.max].include? triple[1] }. 
     map { |_,n,_| n }. 
     unshift(arr.first). 
     push(arr.last) 
end 

例

arr = [33, 53, 12, 64, 50, 41, 45, 21, 97, 35, 47, 92, 39, 0, 93, 55, 40, 
     46, 69, 42, 6, 95, 51, 68, 72, 9, 32, 84, 34, 64, 6, 2, 26, 98, 3, 
     43, 30, 60, 3, 68, 82, 9, 97, 19, 27, 98, 99, 4, 30, 96, 37, 9, 78, 
     43, 64, 4, 65, 30, 84, 90, 87, 64, 18, 50, 60, 1, 40, 32, 48, 50, 76, 
     100, 57, 29, 63, 53, 46, 57, 93, 98, 42, 80, 82, 9, 41, 55, 69, 84, 
     82, 79, 30, 79, 18, 97, 67, 23, 52, 38, 74, 15]  

a = longest_wiggle(arr) 
    #=> [33, 53, 12, 64, 41, 45, 21, 97, 35, 92, 0, 93, 40, 69, 6, 95, 51, 72, 
    # 9, 84, 34, 64, 2, 98, 3, 43, 30, 60, 3, 82, 9, 97, 19, 99, 4, 96, 9, 
    # 78, 43, 64, 4, 65, 30, 90, 18, 60, 1, 40, 32, 100, 29, 63, 46, 98, 42, 
    # 82, 9, 84, 30, 79, 18, 97, 23, 52, 38, 74, 15] 
a.size 
    #=> 67 

說明

步驟如下。

arr = [3, 4, 4, 5, 2, 3, 7, 4] 

enum1 = arr.each_cons(2) 
    #=> #<Enumerator: [3, 4, 4, 5, 2, 3, 7, 4]:each_cons(2)> 

我們可以看到這個枚舉器將生成​​的元素轉換爲一個數組。

enum1.to_a 
    #=> [[3, 4], [4, 4], [4, 5], [5, 2], [2, 3], [3, 7], [7, 4]] 

繼續，刪除每組連續的相等元素中除一個以外的所有元素。

d = enum1.reject { |a,b| a==b } 
    #=> [[3, 4], [4, 5], [5, 2], [2, 3], [3, 7], [7, 4]] 
e = d.map(&:first) 
    #=> [3, 4, 5, 2, 3, 7] 

添加最後一個元素。

f = e.push(arr.last) 
    #=> [3, 4, 5, 2, 3, 7, 4] 

接下來，找到山峯和山谷底部。

enum2 = f.each_cons(3) 
    #=> #<Enumerator: [3, 4, 5, 2, 3, 7, 4]:each_cons(3)> 
enum2.to_a 
    #=> [[3, 4, 5], [4, 5, 2], [5, 2, 3], [2, 3, 7], [3, 7, 4]] 
g = enum2.select { |triple| [triple.min, triple.max].include? triple[1] } 
    #=> [[4, 5, 2], [5, 2, 3], [3, 7, 4]] 
h = g.map { |_,n,_| n } 
    #=> [5, 2, 7] 

最後，加上第一個和最後一個值arr。

i = h.unshift(arr.first) 
    #=> [3, 5, 2, 7] 
i.push(arr.last) 
    #=> [3, 5, 2, 7, 4]