調試最長遞增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-紅寶石

回答

相關問題