今天是我們學習最長遞增子序列算法的第三天，我們終於要開始寫代碼了。

我假設看到這裡的你有先認真看完前兩天的內容，或許你可能看了但沒全看懂，就像去年我剛學這個算法的時候一樣，感覺這東西他喵的是人想出來的！？所以今天寫代碼的過程中我也會逐步說明，但最好還是先把前兩天的進度看完，才好和今天的內容對照著學。

俗話說程序員三日不寫代碼便覺面目可憎，今天是時候該付諸實戰了。讓我們新建檔案/src/runtime-core/sequence.ts，並暴露一個方法。

export default (arr: number[]) => {
  const result = [0];
  const prevIdxs: number[] = [];
};

這個方法接收一個陣列，也就是我們要從中找出最長遞增子序列的父陣列。
並在其中宣告兩個陣列result及prevIdxs，分別記錄子序列以及父陣列每項在被記入子序列時，其在子序列的前項。

然後我們遍歷arr：

arr.forEach((num, i) => {
  const last = result[result.length - 1];
  if (num > arr[last]) {

  } else {

  }
});

宣告一個last代表子序列的最後一項，並比較arr當前的項num，是否大於result末項在arr中對應的項。

如果大於代表目前我們遍歷到的這個num確實是遞增的，我們可以直接把它的索引推到result中，並且記錄它在result的前項，這會是比較簡單好處理的情況。因此我們先從這兒下手：

if (num > arr[last]) {
  result.push(i);
  prevIdxs[i] = last;
}

else的情況就比較麻煩一些，我們必須替換在維持遞增的前提下最小的項，這會需要用到二分查找算法。

所謂二分查找算法，就有點像是猜數字遊戲（誒……我的年齡暴露了？）。

我在心裡想一個1~100的數字，你猜我想的是多少，我會告訴你你猜的太大或太小。在這種猜數字遊戲，你先猜50，如果太小你再猜75，如果還是太小你再猜87，這樣在較多的情況下會比從1開始一個一個慢慢猜來得快速。

也就是當你要從一個順序固定的陣列中找尋符合條件的某個數，先從這個陣列的正中間開始判斷，太小就再往起點和中點的正中間找，太大就往中點和終點的正中間找，然後不斷重複直到找到為止。

let start = 0
let end = result.length - 1
while (end > start) {
  const middleIdx = ((start + end) / 2) | 0
  if (num > arr[result[middleIdx]]) start = middleIdx + 1
  else end = middleIdx
}

| 0和Math.floor()相同效果，都是取整。

當跳脫迴圈，start跟end會相等，都是result中，在arr對應的項剛好比num大的最小項，也就是我們要取代掉的項。

所以接下來就是用比較小的num的索引取代掉result[start]了。

result[start] = i;
prevIdxs[i] = result[start - 1];

此時我們的sequence.ts應該長這樣：

export default (arr: number[]) => {
  const result = [0];
  const prevIdxs: number[] = [];

  arr.forEach((num, i) => {
    const last = result[result.length - 1];
    if (num > arr[last]) {
      result.push(i);
      prevIdxs[i] = last;
    } else {
      let start = 0;
      let end = result.length - 1;
      while (end > start) {
        const middleIdx = ((start + end) / 2) | 0;
        if (num > arr[result[middleIdx]]) start = middleIdx + 1;
        else end = middleIdx;
      }

      result[start] = i;
      prevIdxs[i] = result[start - 1];
    }
  });
};

我們完成了arr的遍歷，記錄每一項的索引被寫入result後它在result中的前一項。接下來我們要從result的末尾往前遍歷，把每項的前一項替換成它在prevIdxs對應的索引。

for (let i = result.length - 1; i > 0; i--) {
  result[i - 1] = prevIdxs[result[i]];
}

最後把result給return出去即可。此時我們的sequence.ts應該長這樣：

export default (arr: number[]) => {
  const result = [0];
  const prevIdxs: number[] = [];

  arr.forEach((num, i) => {
    const last = result[result.length - 1];
    if (num > arr[last]) {
      result.push(i);
      prevIdxs[i] = last;
    } else {
      let start = 0;
      let end = result.length - 1;
      while (end > start) {
        const middleIdx = ((start + end) / 2) | 0;
        if (num > arr[result[middleIdx]]) start = middleIdx + 1;
        else end = middleIdx;
      }

      result[start] = i;
      prevIdxs[i] = result[start - 1];
    }
  });

  for (let i = result.length - 1; i > 0; i--) {
    result[i - 1] = prevIdxs[result[i]];
  }

  return result;
};

我們再來給它從頭過一次。

先創建兩個陣列result及prevIdxs，分別代表子序列和父陣列各項索引在子序列中的前項。這個子序列result會在遍歷父陣列arr時，遇大則推，遇小則替，最終將會變成父陣列arr的最長遞增子序列。而prevIdxs就是在arr的每一項索引被放入result時，它在result中的前一項。也就是說這個prevIdxs會跟arr一樣長，arr的每一項在prevIdxs都能找到對應的項。

接著我們遍歷arr，遇大則推沒甚麼問題，遇小則替，要替的就是比它大的最小項索引，因此用二分查找。找到以後就是把result中的那一項換成遍歷到的索引，同時也記錄它在result中的前一項。

最後再從尾端往回，把result的每一項都換回它真正的前項，這個result就是我們要找的最長遞增子序列。

明天我們將利用這個封裝好的方法，來算出不需要重新渲染的子節點，我們將以此完成diff算法以及renderer.ts。

githubmain分支commit「[Day 19] runtime-core——最長遞增子序列 - 3」