longest subsequence: missing last element-CodePudding

Hi guys I'm working on the longest subsequence algorithm, the idea is to find the subsequence of numbers from an array. I'm using Ruby, so far I'm missing the last number of the subsequence, this is my code:

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

The code has a bug: the last element will never be part of the secuencia_mayor array due to the conditional, my question is: what should I change in the code to overcome this issue?

Thanks a lot

CodePudding user response：

To use the approach you have taken you need to save the longest known sequence found so far (or its starting index and length) as you loop through the elements of the array. Here is one way to do that.

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]

Another way, which is more Ruby-like, is to use 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]

The steps are as follows.

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]
d.size
  #=> 4

We can see the elements that enum will generate and pass to max_by by converting the enumerator to an array:

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

enum.max_by(&:size) is shorthand for enum.max_by { |e| e.size }.