「那是雜魚的思維。」——鹿紫雲

之前我們討論了新舊子節點（以下簡稱為新子、舊子）的比對，我們會先從頭比對，再從尾比對，確保新、舊子僅有中間不同，示意範例如下：
舊：AB(CDEFG)HI
新：AB(GDEFC)HI

在這個範例中，A、B、H、I都是能從首或尾比對得知無須重新渲染的子節點，我們剩下的工作只有比對新舊子節點被括號包起來的部分。

舊：CDEFG
新：GDEFC

可以看到只有C和G的位置對調了，也就是說其實D、E、F都是不用重新渲染的，可以直接維持舊有的dom元素，僅將C和G重新渲染到正確的位置即可。那麼我們是怎麼找到D、E、F的呢？比較敏銳的小夥伴可能已經注意到了，這正是我們昨天玩的遊戲，尋找最長遞增子序列的索引。

只要找到最長遞增子序列的索引，我們就能保留最多不必重新渲染的dom元素，用CPU能高速替我們處理的邏輯運算代替費時的dom操作。

最長遞增子序列的應用

上述案例可以這麼理解：

新子第0項G是舊子的第4項，第1項D是舊子的第1項……新子第4項C是舊子的第0項。將新子的key對舊子的索引做映射，我們可以得到一個陣列[4,1,2,3,0]代表新子是舊子中的第幾項。只要找到這個陣列的最長遞增子序列，這些項就是舊子中不需要重新渲染的dom元素。

如此一來，我們便將找出舊子中不需要重新渲染的dom元素這個需求，抽象成了找出最長遞增子序列。

實現最長遞增子序列

昨天我們探討到了最長遞增子序列的實現方法，如果準備一堆陣列來存儲可能是最長遞增子序列的候補，就能找出真正的最長遞增子序列，但那是雜魚的思維。

我們要用僅有兩個陣列的空間複雜度，找出最長遞增子序列。

兩個陣列

僅用兩個陣列，第一個用來存的自然是要返回的結果，也就是我們最終找到的最長遞增子序列。那麼另外一個陣列是拿來存甚麼的呢？答案是父陣列每一項的索引在遞增子序列中的前一項。

在子序列中的前一項是甚麼意思，而我們又要如何用這兩個陣列找出最長遞增子序列的索引呢？且聽我先把這個算法的步驟說完。

實踐方式

先來演示一個錯誤的方法。
宣告一個代表子序列的陣列result，遍歷父陣列，將父陣列被遍歷到的項的索引寫入子序列。如果被遍歷到的這項（arr[i]）比子序列末項在父陣列中對應的項（arr[result[result.length - 1]]）更大，就直接放在子序列result的末項；如果比較小，就在維持子序列遞增的前提下，將最小的項換成遍歷到的項的索引。

這樣講可能很抽象，就讓我們拿上面提到的[4,1,2,3,0]來舉例吧：

我們先遍歷父陣列，它的第0項是4，但子序列中還沒有能比大小的末項，因此直接將索引0推入子序列。

接著遍歷到父陣列第1項是1，1顯然比子序列末項0在父陣列中對應的項4來得小，因此直接用索引1取代掉子序列的第0項。

然後我們遍歷父陣列的第2項是2，2比子序列末項1在父陣列中對應的項1來得大，因此推入子序列。

我們再遍歷父陣列第3項是3，3比2大，因此在子序列推入3。

截至目前為止，這個策略都是成功的，但當遍歷到了父陣列第4項是0，0比子序列末項在父陣列中對應的項3小……呃我是說比3還要小，因此我們要找子序列各項在父陣列中對應的項，在維持子序列遞增的前提下，將最小的項換成4，也就是將子序列中的1換成4。

這樣找到的最長遞增子序列就成了[4,2,3]，但正確答案理應是[1,2,3]才對。顯然在遍歷父陣列第1項時取代掉第0項是正確的，但如果父陣列尾端遞增的項不夠多，取代掉較小的項會出問題。

因此這邊就需要第二個陣列來幫忙了。

記錄子序列中的前項

讓我們重新做一次[4,1,2,3,0]這個例子，只是我們除了把父陣列遍歷到的項的索引放入子序列以外，我們還記錄父陣列的每一個索引在被放入子序列時，它在子序列中的前項是誰。

先遍歷第0項是4，子序列是空的，因此將索引0寫入子序列。此時子序列為空，並沒有前項，方便起見我們用-號記錄，代表undefined。

再遍歷到第1項是1，1比子序列末項0在父陣列中對應的項4小，因此取代它。由於子序列唯一一項被取代了，沒有前項，因此前項仍記入-號。

再遍歷第2項2，2比子序列末項1在父陣列中對應的項1大，因此推入子序列中。由於此時子序列有第0項1，因此前項記入1。

再遍歷第3項3，3比子序列末項2在父陣列中對應的項2大，因此推入子序列中，並記入子序列中的前項2。

遍歷第4項0，0比子序列末項3在父陣列中對應的項3小，因此在維持遞增的前提下，將子序列最小項1替換成4。由於被替換掉的1是子序列第0項，再往前就沒項了，因此在前項記入-號。

然後就是我們記錄的前項派上用場的時候了。

我們只要將子序列從末項往前項遍歷，把每一項的前一項都換成我們先前記錄的前項，就能找到最長遞增子序列的索引！

要是難以置信，不妨可以試試。我們從尾端遍歷子序列，子序列的末項是3，前項的第3項是2，因此將子序列末項的上一項換成2。

然後子序列末項的上一項是2，前項的第2項是1，因此將子序列中2的再前一項換成1。

子序列中2的上一項就是首項了，不用再繼續置換前一項。此時子序列竟是[1,2,3]，我們成功只用兩個陣列的空間複雜度解決了這個尋找最長遞增子序列的索引的問題。

原理

為什麼只要記錄前項，並把子序列中的每項的前一項都換成先前在前項記錄的索引，就能找到最長遞增子序列呢？是這樣的，在我們沒有記錄前項的那個出錯的範例中，可以觀察到當父陣列的尾端沒有夠長的遞增子序列，但卻又比目前記錄的遞增子序列末項更小時，我們會誤將原本記錄的子序列的某一項換成錯誤的項。

也就是說關鍵在於子序列的末項。就算子序列中有某些不該被取代的項被取代了，只要它的末項不曾被取代過，我們都能用子序列末項在前項這個陣列中的索引，找到它在子序列中真正正確的前項。

你可能會說如果子序列的末項也被取代了怎麼辦呢？這樣我們不就找不到被取代前的子序列末項真正的前項了嗎？實際上我們也不用找了，因為子序列的末項能被取代，代表它前面已經有比原本的末項更多的遞增項。因此我們可以確保，在遍歷完父陣列後，從子序列的末項往前回推，找到的每一個前項都會是正確的。

如果還是覺得很抽象，我們不妨可以再多看幾個例子。

更多範例

我用js隨機生成了7個數組成的陣列arr = [9, 3, 9, 2, 4, 0, 5]，我們就用這7個數來試試看吧。

遍歷arr，將第0項的索引0寫入子序列，這個索引在子序列中沒有前項。

繼續遍歷arr，第1項3小於子序列末項0在父陣列中對應的項9，因此將子序列中的0替換成1，1在子序列中仍沒有前項。

arr第2項9大於子序列末項1在父陣列中對應的項3，因此將索引2推入子序列中，其在子序列中的前項為1。

arr第3項2小於子序列末項2在父陣列中對應的項9，因此在維持子序列遞增的前提下，將最小的項換成3，也就是將第0項1（在父陣列中對應的項為3，大於arr第3項的2）換成3，此時3在子序列中沒有前項。

arr第4項4同樣小於子序列末項在父陣列中對應的9，因此同樣在維持子序列遞增的前提下，將最小的項換成4，也就是將第1項2（在父陣列中對應的項為9，大於arr第4項的4）換成4，此時4在子序列中的前項為3。

arr第5項小於子序列末項在父陣列中對應的4，因此取代子序列第0項3，此時沒有前項。

arr第6項的5大於子序列末項在父陣列中對應的4，因此推入子序列，此時它在子序列的前項是4。

此時我們完成了父陣列arr的遍歷，接下來從子序列末尾依序把各項的前一項換成前項陣列中記錄的索引：

得到最長遞增子序列索引[3,4,6]。

如果還是有那麼點似懂非懂的感覺，可以自己在控制台隨機生成幾個陣列，然後按照上面的步驟去遍歷它，再從子序列尾端往前替換每一項，多試幾次就會越來越清楚這個算法是如何運作的，同時也會逐漸體會到它的精妙。

然後明天，我們將會把這個算法寫成代碼，之後好用來算出不必重新渲染的子節點。