最长子序列：缺少最后一个元素

Question

大家好我正在研究最长子序列算法，我的想法是从数组中找到数字的子序列。我正在使用 Ruby，到目前为止我遗漏了子序列的最后一个数字，这是我的代码：

def sequence_length1(array)
  array.sort! 
  secuencia_mayor = []
  array.each_with_index do |numero, indice|
    numero + 1 == array[indice+1] ? secuencia_mayor << numero  : ''
  end
  return secuencia_mayor
end

p sequence_length1([100, 4, 200, 1, 3, 2]) #length=4
p sequence_length1([29, 27, 28, 55, 100, 84]) #length=3

代码有一个错误：由于条件的原因，最后一个元素永远不会成为 secuencia_mayor 数组的一部分，我的问题是：我应该在代码中更改什么来克服这个问题？

非常感谢

Answer 1

要使用您采用的方法，您需要在遍历数组元素时保存迄今为止找到的最长已知序列（或其起始索引和长度）。这是一种方法。

def sequence_length1(array)
  array.sort!
  secuencia_mayor = []
  candidate = []
  array.each do |numero|
    if candidate.empty? || candidate.last + 1 == numero
      candidate << numero
    else
      secuencia_mayor = candidate.dup if candidate.size > secuencia_mayor
      candidate = []
    end
  end
  secuencia_mayor = candidate.dup if candidate.size > secuencia_mayor
  secuencia_mayor
end

sequence_length1 [100, 4, 200, 1, 3, 2]
  #=> [1, 2, 3, 4]
sequence_length1([29, 27, 28, 55, 100, 84]) #length=3
  #=> [27, 28, 29]

另一种更Ruby-like的方法是使用Enumerable#slice_when and Enumerable#max_by.

def seq(arr)
  arr.sort.slice_when { |a,b| b != a + 1 }.max_by(&:size)
end

seq [100, 4, 200, 1, 3, 2]
  #=> [1, 2, 3, 4]
seq [29, 27, 28, 55, 100, 84]
  #=> [27, 28, 29]

步骤如下

arr = [100, 4, 200, 1, 3, 2]
c = arr.sort
  #=> [1, 2, 3, 4, 100, 200]
enum = c.slice_when { |a,b| b != a + 1 }
  #=> #<Enumerator: #<Enumerator::Generator:0x00007fa9fd913238>:each>
d = enum.max_by(&:size)
  #=> [1, 2, 3, 4]

我们可以看到 enum 将生成并通过将枚举器转换为数组传递给 max_by 的（三个）元素：

enum.to_a
  #=> [[1, 2, 3, 4], [100], [200]]

enum.max_by(&:size) 是 shorthand 对于 enum.max_by { |e| e.size }。

也可以使用 slice_when 的近亲 Enumerable#chunk_while:

[100, 4, 200, 1, 3, 2].sort.chunk_while { |a,b| b == a + 1 }.max_by(&:size)
  #=> [1, 2, 3, 4]

最长子序列：缺少最后一个元素

longest subsequence: missing last element

ruby

algorithm

data-structures