从一个序列中找出最长的递增子序列:

例如对于序列A:

[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

最长递增子序列为: 0, 2, 6, 9, 11, 15

动态规划 O(N^2)

对于序列A

LIS(i) = Max(LIS(j)) // j < i && A[i] > A[j]


// dp[i]表示以arr[i]结尾的lis长度

const lis = (arr) => {
  const { length } = arr
  const dp = Array(length).fill(1)
  let maxLen = 1
  for (let i = 1; i < length; i++) {
    for(let j = 0; j < i; j++) {
      if(arr[i] > arr[j] && dp[j] + 1 > dp[i]) {
        dp[i] =  dp[j] + 1
      }
    }
    maxLen = Math.max(maxLen, dp[i])
  }
  return maxLen
}

动态规划 O(NlogN)

上面的算法主要的缺点在于内层循环,每次都需要比较来找出i以前的最长序列

有没有什么办法优化呢?

arr = [0, 8, 4, 12, 2, 10]

开辟一个数组dp,dp[i]表示长度为i + 1的lis的最小结尾,初始化dp = [ arr[0] ], 然后遍历arr超出最长lis

Step1: dp[0] = 0,表示长度为1的lis的最小结尾为0, dp = [ 0 ]

Step2: 把8放进去,因为8 > 0,所以dp[1] = 8,表示长度为2的lis的最小结尾为8, dp = [ 0, 8 ]

Step3: 把4放进去,因为4 < 8,所以dp[1] = 4,表示长度为2的lis的最小结尾为4, dp = [ 0, 4 ]

Step4: 把12放进去,因为12 > 4,所以dp[2] = 4,表示长度为3的lis的最小结尾为4, dp = [ 0, 4, 12 ]

Step5: 把2放进去,因为2 < 4,所以dp[1] = 2,表示长度为2的lis的最小结尾为2, dp = [ 0, 2, 12 ]

Step6: 把10放进去,因为10 < 12,所以dp[2] = 10,表示长度为3的lis的最小结尾为10, dp = [ 0, 2, 10 ]

结果为dp.length3

dp是有序递增的,因此可以采用二分法查找下一个数字的位置


export const BS = (arr, start, end, value) => {
  while (start !== end) {
    const mid = Math.floor((start + end) / 2)
    const vMid = arr[mid]
    if (value > vMid) {
      start = mid + 1
    } else {
      end = mid
    }
  }
  return start
}

export const lisWithBS = (arr) => {
  const { length } = arr
  const dp = [arr[0]]
  for (let i = 1; i < length; i++) {
    if (arr[i] >= dp[dp.length - 1]) {
      dp.push(arr[i])
    } else {
      const index = BS(dp, 0, dp.length - 1, arr[i])
      dp[index] = arr[i]
    }
  }
  return dp
}


如何获取实际的LIS而非长度呢?

用数组res记录每个长度的序列,数组lastIndex来记录每个序列的最后一元素在arr中的位置

例如:

对于 arr = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]

Setp1: 初始化 res = [ [arr[0]] ], lastIndex = 0

| 0 | 0 |

Step2: +8

| 0 | 0 |

| 0 8 | 1 |

Step3: +4

| 0 | 0 |

| 0 4 | 2 |

Step4: +12

| 0 | 0 |

| 0 4 | 2 |

| 0 4 12 | 3 |

Step5: +2

| 0 | 0 |

| 0 2 | 4 |

| 0 4 12 | 3 |

Step6: +10

| 0 | 0 |

| 0 2 | 4 |

| 0 4 10 | 5 |

然后,因为我们修改后的lastIndex是5,比前一行大,替换

| 0 | 0 |

| 0 2 | 4 |

| 0 2 10 | 5 |

…重复,最后

| 0 | 0

| 0 1 | 8

| 0 1 3 | 12

| 0 1 3 7 | 14

| 0 2 6 9 11 | 13

| 0 2 6 9 11 15 | 15


export const lisWithBS = (arr) => {
  const { length } = arr
  const dp = [arr[0]]
  const lastIndex = [0]
  const res = [
    [arr[0]]
  ]
  for (let i = 1; i < length; i++) {
    if (arr[i] >= dp[dp.length - 1]) {
      dp.push(arr[i])
      res.push([...res[res.length - 1], arr[i]])
      lastIndex.push(i)
    } else {
      const index = BS(dp, 0, dp.length - 1, arr[i])
      dp[index] = arr[i]
      const len = res[index].length
      lastIndex[index] = i
      if (lastIndex[index] > lastIndex[index - 1]) {
        res[index] = [...res[index - 1], arr[i]]
      } else {
        res[index][len - 1] = arr[i]
      }
    }
  }
  return res
}