调试最长递增Subsequence-红宝石

鉴于整数的排序的数组，发现最长递增子序列的长度。

例如，给定[10，9,2，5,3，7，101，18]，最长递增子是[2，3，7，101]，因此长度为4。请注意，可能有多个LIS组合，它只有需要您返回长度。

你的算法应该以O（n2）的复杂度运行。

后续行动：你可以改善它到O（n日志n）的时间复杂性？

试图实施第一个蛮力解决方案，它基本上是一种递归方法来生成每个增加的子序列，然后抓取最大长度的解决方案。在我实现这个之后，我将使用动态编程进行优化。我发现自己越来越糊涂的蛮力的实施有点force--这里是我的代码：

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子序列。

正如你所知道的，这将创建两个相同的线路，我不知道如何组织代码，使得两个独立的事情发生和最大变量包含最终值。有关如何相应调整此代码的任何想法？

来源

2017-02-18 Sunny

我没有回答你的问题，因为我不能跟你在做什么。（代码的前两行是特别奇怪的。神器，也许？）我没有，但是，提供了一个动态规划的解决方案（下一步我看到）。我认为DP肯定是去这里的路。这是O（n^2），但我不认为有更快的解决方案。 –

前两个实际上应该被注释掉 - 它们没有让网站的用户知道什么输入和输出应该是。我一定会分析你所提供的解决方案，但它有助于我了解我哪里错了我的思维过程，而不是简单地寻找一个解决方案/读取它的解释。我删除了前两行 - 我可以为你编辑其他的东西或解释一些东西吗？ – Sunny

我已经使用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（如果序列增加），在这种情况下，其长度为2。

更一般地，如果LIS开始于索引i，它最终可能有或继续，j是在LIS下一个索引，其中i+1 <= j <= arr.size-1和arr[i] < arr[j]。对于任何此类j我们已经计算的LIS如果序列始于指数j，让我们知道，从指数j，i和j共享同一个LIS 如果开始i的LIS的下一个元素是j。因此，获得LIS开始i我们采取了最大的LIS的尺寸对于其j和arr.size-1之间i+1arr[i] < arr[j]，并添加1，除非没有索引j针对arr[i] < arr[j]，在这种情况下，LIS为i在i结束。

动态规划溶液搁置在最优，其在这里是观察的原理，如果索引i是LIS的一员，是也是LIS的成员不依赖于指数j, j > i的收集索引j, j < i是该LIS的成员。换言之，从指数i前进的最佳方式并不取决于我们如何到达那里。

为了表明我已经添加了一些看跌期权报表计算的细节longest_increasing_sequence：

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]

来源

2017-02-18 02:51:45

调试最长递增Subsequence-红宝石

回答

相关问题