算法 - 最长摆动子序列

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]