例子：3 1 2 7 5 8 6 9 4

v1.0.0

从前到后循坏，找到所有的可能性

const arr = [3, 1, 2, 7, 5, 8, 6, 9, 4]for (let i = 0; i < arr.length; i++) {    const n = arr[i]    console.log(i, n)    // todo}

i = 0，可能最长组合：

3 ... // i = 0, n = 3

i = 1，可能最长组合：

3 ... // i = 0, n = 31 ... // i = 1, n = 1

i = 2，可能最长组合：

3 ...   // i = 0, n = 31 ...   // i = 1, n = 11 2 ... // i = 2, n = 2

由此类推：
i = 9，最终组合：

0 1 2 3 4 // 序号3         // i = 0, n = 31         // i = 1, n = 11 2       // i = 2, n = 21 2 7     // i = 3, n = 71 2 5     // i = 4, n = 51 2 7 8   // i = 5, n = 81 2 5 81 2 5 6   // i = 6, n = 61 2 7 8 9 // i = 7, n = 91 2 5 8 91 2 5 6 91 2 4     // i = 8, n = 4

找到了最长的递增子序列为1 2 7 8 9，1 2 5 8 9，1 2 5 6 9

v2.0.0

咱们能够发现

1 2 7 ...1 2 5 ...

1 2 5能带来的可能，蕴含了1 2 7能带来的所有可能

1 2 5 8 ...1 2 5 6 ...

1 2 5 6能带来的可能，蕴含了1 2 5 8能带来的所有可能

所以咱们只须要用到雷同序号下的最小值

以 i = 5, n = 8 为例：

0 1 2 // 序号3 ...1 ...1 2 ...1 2 7 ...1 2 5 ...

变成

3 ...1 ...1 2 ...1 2 7 ...1 2 5 ...1 2 5 8 ...

序号2，对应的值[7, 5]，最小值是5，这里只需用到1 2 5

下面最终组合：

3         // i = 0, n = 31         // i = 1, n = 11 2       // i = 2, n = 21 2 7     // i = 3, n = 71 2 5     // i = 4, n = 51 2 5 8   // i = 5, n = 81 2 5 6   // i = 6, n = 61 2 5 6 9 // i = 7, n = 91 2 4     // i = 8, n = 4

找到了最长的递增子序列为1 2 5 6 9，数据过大时，大大降低了循环次数

留神：如果是要找到所有的可能性，只能就义性能，但很多时候，咱们只须要找到其中最长的一种可能就行了，比方：vue的虚构节点比照

v3.0.0

后面中，每次都须要先找到对应序号下最小的一位，而后再来比照，其实咱们能够把每个序号上面的最小值用一个数组（min_arr）记录下来

0 1 2 3 4 // 序号3         // i = 0, n = 3, min_arr = [3]1         // i = 1, n = 1, min_arr = [1]1 2       // i = 2, n = 2, min_arr = [1, 2]1 2 7     // i = 3, n = 7, min_arr = [1, 2, 7]1 2 5     // i = 4, n = 5, min_arr = [1, 2, 5]1 2 5 8   // i = 5, n = 8, min_arr = [1, 2, 5, 8]1 2 5 6   // i = 6, n = 6, min_arr = [1, 2, 5, 6]1 2 5 6 9 // i = 7, n = 9, min_arr = [1, 2, 5, 6, 9]1 2 4     // i = 8, n = 4, min_arr = [1, 2, 4, 6, 9]

由v2.0.0可知，咱们只须要和每个序号下最小值来比照，也就是以后n间接和min_arr比照

思路：

  1. 如果以后n比min_arr最初一项大，则间接放到开端，如：i = 3, n = 7，7比2大，7间接放在2的前面
  2. 如果以后n比min_arr最初一项小，从后往前循环min_arr，找到比n小的一项为止，n放在其前面，此时原前面这一项必定比n大，所以替换原前面这一项；如：i = 8, n = 4，始终往前找，2比4小，进行循环，4放在2前面，2前面原来的5必定是比4大的，不然到5就应该完结了，所以间接替换原来的5（代码中会采纳二分法查找）

v4.0.0

此时咱们发现最终失去的min_arr的值尽管是不正确的，然而最初一位的值必定是正确的，如果咱们转变思维，标记最初一位在谁的前面，而后一层一层的往前标记，这个事件是不是就成了，如

0 1 2 3 4 // 序号3         // i = 0, n = 3, min_arr = [3], 3后面为undefined1         // i = 1, n = 1, min_arr = [1], 1后面为undefined1 2       // i = 2, n = 2, min_arr = [1, 2], 2后面为11 2 7     // i = 3, n = 7, min_arr = [1, 2, 7], 7后面为21 2 5     // i = 4, n = 5, min_arr = [1, 2, 5], 5后面为21 2 5 8   // i = 5, n = 8, min_arr = [1, 2, 5, 8], 8后面为51 2 5 6   // i = 6, n = 6, min_arr = [1, 2, 5, 6], 6后面为51 2 5 6 9 // i = 7, n = 9, min_arr = [1, 2, 5, 6, 9], 9后面为61 2 4     // i = 8, n = 4, min_arr = [1, 2, 4, 6, 9], 4后面为2

先找到9，而后6，而后5，而后2，而后1，此时就找到了最长的递增子序列为1 2 5 6 9

最终

在程序中咱们须要把值对应成索引，能力更好的找到其地位

0 1 2 3 4 5 6 7 8 // 索引3 1 2 7 5 8 6 9 4 // 值

下面v4.0.0变成

0 1 2 3 4 // 序号0         // i = 0, min_arr = [0], 0后面为undefined1         // i = 1, min_arr = [1], 1后面为undefined1 2       // i = 2, min_arr = [1, 2], 2后面为11 2 3     // i = 3, min_arr = [1, 2, 3], 3后面为21 2 4     // i = 4, min_arr = [1, 2, 4], 4后面为21 2 4 5   // i = 5, min_arr = [1, 2, 4, 5], 5后面为41 2 4 6   // i = 6, min_arr = [1, 2, 4, 6], 6后面为41 2 4 6 7 // i = 7, min_arr = [1, 2, 4, 6, 7], 7后面为61 2 8     // i = 8, min_arr = [1, 2, 8, 6, 7], 8后面为2

先找到索引7，而后6，而后4，而后2，而后1，此时索引为1 2 4 6 7，对应的最长的递增子序列值为1 2 5 6 9

源代码

function getSequence(arr:number[]) {  const len = arr.length  const min_arr = [0] // 存储最小的索引，以索引0为基准  const prev_arr = arr.slice() // 贮存后面的索引，slice为浅复制一个新的数组  let last_index  let start  let end  let middle  for (let i = 0; i < len; i++) {    let arrI = arr[i]    // 1. 如果以后n比min_arr最初一项大    last_index = min_arr[min_arr.length - 1]    if (arr[last_index] < arrI) {      min_arr.push(i)      prev_arr[i] = last_index // 后面的索引      continue    }    // 2. 如果以后n比min_arr最初一项小（二分类查找）    start = 0    end = min_arr.length - 1    while(start < end) {      middle = (start + end) >> 1 // 相当于Math.floor((start + end)/2)      if (arr[min_arr[middle]] < arrI) {        start = middle + 1      } else  {        end = middle      }    }    if (arr[min_arr[end]] > arrI) {      min_arr[end] = i      if (end > 0) {        prev_arr[i] = min_arr[end - 1] // 后面的索引      }    }  }  // 从最初一项往前查找  let result = []  let i = min_arr.length  let last = min_arr[i - 1]  while(i-- > 0) {    result[i] = last    last = prev_arr[last]  }  return result}console.log(getSequence([3, 1, 2, 7, 5, 8, 6, 9, 4]))// 索引：[ 1, 2, 4, 6, 7 ]// 值： [ 1, 2, 5, 6, 9 ]