解釋算法來解決'最長的遞增子序列'問題

我一直試圖理解這個算法過去兩個小時，但似乎無法得到它。有人可以用簡單易懂的方式解釋嗎？解釋算法來解決'最長的遞增子序列'問題

function lis_length(a) 
    n := a.length 
    q := new Array(n) 
    for k from 0 to n: 
     max := 0; 
     for j from 0 to k, if a[k] > a[j]: 
      if q[j] > max, then set max = q[j]. 
     q[k] := max + 1; 
    max := 0 
    for i from 0 to n: 
     if q[i] > max, then set max = q[i]. 
    return max;

來源

2011-09-02 missingfaktor

用鉛筆和紙張上的十元素數組遍歷代碼。或者返回到該功能的文檔。 –

^@ RaymondChen 這是如此無益。最好不要發佈任何內容，而不要提出這樣的建議。它降低了本網站的答案質量，它只會損害社區並延伸自己。 – guribe94

在第一個（雙）循環終止之後，q[i]是結束於位置i的最長增加子序列的長度。

要看到雙迴路是如何工作的，假設q[j]已經包含在j位置結束最大的遞增子的長度，但只爲j0和k-1之間。鑑於此，你將如何計算q[k]？

那麼，你會發現所有的j與j < k和a[j] < a[k]的，看看哪些相應q[j]值最大，增加一個，並在q[k]藏匿該值。這正是內循環所做的。

因此，在進入內循環時，q[j]已在0和k-1之間具有正確的j值。在出口處，它也具有正確的值k。因此，雙循環退出時，q[i]對於0和n之間的所有i都具有正確的值。

最後一個循環只是選擇其中最大的那個，這就是答案。

來源

2011-09-02 14:45:25 Nemo

對於每個元素設定當前元素製成的元件的最長子的計數通過當前元素元件之前最長子之一的長度遞增，使得它們的最大值大於當前元素的值小。

該算法採用正數的數組（不能具有零或更少的元素）。

來源

2011-09-02 14:28:15 Dialecticus

解釋算法來解決'最長的遞增子序列'問題

回答

相關問題