ruby - 调试最长递增子序列-Ruby

我正在通过Leetcode解决以下问题：
给定一个未排序的整数数组，求最长递增子序列的长度。
例如，给定[10，9，2，5，3，7，101，18]，最长
增加的子序列是[2，3，7，101]，因此长度是4。
注意，可能有多个LIS组合，它只是
你必须返回长度。
您的算法应该以O（N2）复杂度运行。
后续：你能把它提高到O（n log n）的时间复杂度吗？
尝试实现第一个强力解决方案，它本质上是一种递归方法，生成每一个递增的子序列，然后获取长度最大的子序列实现之后，我将使用动态编程进行优化。我发现自己对暴力的实现有点困惑——下面是我的代码：

def length_of_lis(nums)
    1 + max_len(nums, 1, nums.first)
end

def max_len(nums, index, prev_number)
    current_num = nums[index]
    max = 0
    return 0 if index >= nums.length
    if current_num > prev_number
        max = [1 + max_len(nums, index + 1, current_num), max].max
    else
        max = [max_len(nums, index + 1, prev_number), max].max
    end
    max = [1 + max_len(nums, index + 1, current_num), max].max

    max
end

现在我知道这显然是不正确的，但我要做的是，在每个数字上，都会发生一些事情1）它是从前一个数字传递的一个函数，如果当前数字大于前一个数字，则继续为lis传递该函数。2）在当前编号处创建新的LIS子序列。
如您所知，这将创建两个相同的行，我不确定如何构造代码，使两个独立的事件发生，并且max变量包含最终值。你对如何相应地调整这个代码有什么想法吗？

最佳答案

我用dynamic programming得到了一个最优解。
代码

def construct_sequence(longest, max_i)
  a = []
  loop do
    a << max_i
    max_i = longest[max_i][:next]
    return a if max_i.nil?
  end
end

def longest_increasing_sequence(arr)
  longest = Array.new(arr.size)
  longest[arr.size-1] = { length: 1, next: nil }
  (arr.size-2).downto(0) do |i|
    best_seq = { length: 1, next: nil }
    (i+1).upto(arr.size-1) do |j|
      next if arr[j] <= arr[i]
      h = longest[j]
      best_seq = { length: 1 + h[:length], next: j } if h[:length] >= best_seq[:length]
    end
    longest[i] = best_seq
  end
  max_i = (0..arr.size-1).max_by { |i| longest[i][:length] }
  construct_sequence(longest, max_i)
end

例子

arr = [10, 9, 2, 5, 3, 7, 101, 18]
a = longest_increasing_sequence(arr)
  #=> [2, 3, 5, 6]
a.each_with_object({}) { |n,h| h[n] = arr[n] }
  #=> {2=>2, 3=>5, 5=>7, 6=>101}

在第二个例子中，我构造了以下20个元素的伪随机数组。

arr = (1..99).to_a.sample(20)
  #=> [80, 75, 13, 12, 85, 16, 41, 89, 93, 56, 74, 18, 37, 24, 27, 63, 47, 83, 25, 44]

longest_increasing_sequence返回组成最长递增序列的arr索引数组。

a = longest_increasing_sequence(arr)
  #=> [2, 5, 11, 13, 14, 15, 17]
a.each_with_object({}) { |n,h| h[n] = arr[n] }
  #=> {2=>13, 5=>16, 11=>18, 13=>24, 14=>27, 15=>63, 17=>83}

解释
数组的每个元素都有一个阶段。状态变量是数组的索引，其中最长递增序列（“lis”）开始。我们从数组的最后一个元素开始，在上面的例子中是arr[19]如果递增序列（“IS”）从那里开始，它也在那里结束这个序列的长度是1。
然后我们回到第18阶段。有两种可能：从该阶段开始的LS的长度1，或在第19阶段继续（如果序列在增加），在这种情况下，LS的长度2。
更一般地，如果LIS开始于indexi，它可能结束于此或继续，其中j是LIS中的下一个索引，其中i+1 <= j <= arr.size-1和arr[i] < arr[j]对于任何这样的j我们已经计算了如果序列开始于indexj，那么我们知道，从indexj，i和j共享相同的lis，如果开始于i的lis的下一个元素是j。因此，为了获得从i开始的LIS，我们取j和i+1之间arr.size-1的最大LIS的大小，并添加arr[i] < arr[j]，除非没有1的指数，在这种情况下，j的LIS结束于arr[i] < arr[j]。
动态规划解依赖于最优性原则，这里的观察是，如果indexi是LIS的成员，那么作为LIS成员的索引i的集合不依赖于作为LIS成员的索引i换言之，从indexj, j > i前进的最佳方式并不取决于我们如何到达那里。
为了显示计算的细节，我在j, j < i中添加了一些puts语句：

def longest_increasing_sequence(arr)
  longest = Array.new(arr.size)
  longest[arr.size-1] = { length: 1, next: nil }
  puts "longest[#{arr.size-1}]=#{longest[arr.size-1]}"
  (arr.size-2).downto(0) do |i|
    best_seq = { length: 1, next: nil }
    puts "i=#{i}"
    puts "  initial best_seq=#{best_seq}"
    (i+1).upto(arr.size-1) do |j|
      puts "    j=#{j}, arr[#{i}]=#{arr[i]}, arr[#{j}]=#{arr[j]}"
      next if arr[j] <= arr[i]
      h = longest[j]
      puts "    h=#{h}"
      puts "    j=#{j} provides new best_seq=#{{length: 1 + h[:length], next: j }}" if
        h[:length] >= best_seq[:length]
      best_seq = { length: 1 + h[:length], next: j } if h[:length] >= best_seq[:length]
    end
    longest[i] = best_seq
  end
  longest.each_index { |i| puts "i=#{i}: #{longest[i]}" }
  max_i = (0..arr.size-1).max_by { |i| longest[i][:length] }
  construct_sequence(longest, max_i)
end

arr = [60, 29, 56, 46, 37, 57, 28, 44]
longest_increasing_sequence(arr)

longest[7]={:length=>1, :next=>nil}
i=6
  initial best_seq={:length=>1, :next=>nil}
    j=7, arr[6]=28, arr[7]=44
    h={:length=>1, :next=>nil}
    j=7 provides new best_seq={:length=>2, :next=>7}
i=5
  initial best_seq={:length=>1, :next=>nil}
    j=6, arr[5]=57, arr[6]=28
    j=7, arr[5]=57, arr[7]=44

i=4
  initial best_seq={:length=>1, :next=>nil}
    j=5, arr[4]=37, arr[5]=57
    h={:length=>1, :next=>nil}
    j=5 provides new best_seq={:length=>2, :next=>5}
    j=6, arr[4]=37, arr[6]=28
    j=7, arr[4]=37, arr[7]=44
    h={:length=>1, :next=>nil}
i=3
  initial best_seq={:length=>1, :next=>nil}
    j=4, arr[3]=46, arr[4]=37
    j=5, arr[3]=46, arr[5]=57
    h={:length=>1, :next=>nil}
    j=5 provides new best_seq={:length=>2, :next=>5}
    j=6, arr[3]=46, arr[6]=28
    j=7, arr[3]=46, arr[7]=44
i=2
  initial best_seq={:length=>1, :next=>nil}
    j=3, arr[2]=56, arr[3]=46
    j=4, arr[2]=56, arr[4]=37
    j=5, arr[2]=56, arr[5]=57
    h={:length=>1, :next=>nil}
    j=5 provides new best_seq={:length=>2, :next=>5}
    j=6, arr[2]=56, arr[6]=28
    j=7, arr[2]=56, arr[7]=44

i=1
  initial best_seq={:length=>1, :next=>nil}
    j=2, arr[1]=29, arr[2]=56
    h={:length=>2, :next=>5}
    j=2 provides new best_seq={:length=>3, :next=>2}
    j=3, arr[1]=29, arr[3]=46
    h={:length=>2, :next=>5}
    j=4, arr[1]=29, arr[4]=37
    h={:length=>2, :next=>5}
    j=5, arr[1]=29, arr[5]=57
    h={:length=>1, :next=>nil}
    j=6, arr[1]=29, arr[6]=28
    j=7, arr[1]=29, arr[7]=44
    h={:length=>1, :next=>nil}
i=0
  initial best_seq={:length=>1, :next=>nil}
    j=1, arr[0]=60, arr[1]=29
    j=2, arr[0]=60, arr[2]=56
    j=3, arr[0]=60, arr[3]=46
    j=4, arr[0]=60, arr[4]=37
    j=5, arr[0]=60, arr[5]=57
    j=6, arr[0]=60, arr[6]=28
    j=7, arr[0]=60, arr[7]=44
i=0: {:length=>1, :next=>nil}
i=1: {:length=>3, :next=>2}
i=2: {:length=>2, :next=>5}
i=3: {:length=>2, :next=>5}
i=4: {:length=>2, :next=>5}
i=5: {:length=>1, :next=>nil}
i=6: {:length=>2, :next=>7}
i=7: {:length=>1, :next=>nil}
  #=> [1, 2, 5]

关于ruby - 调试最长递增子序列-Ruby，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42310237/