#991 | 2022-04-01 19:09:13

最长递增子序列(动态规划 + 二分查找)

function lengthOfLIS (nums) {
    const arr = [] // arr[k] 的值代表 长度为 k+1 子序列 的尾部元素值
    const len = nums.length
    for (let i = 0; i < len; i++) {
        let n = nums[i]
        let left = 0, right = arr.length
        while (left < right) {
            let mid = left + ((right - left) >> 1)
            if (arr[mid] >= n) {
                right = mid
            } else {
                left = mid+1
            }
        }
        arr[left] = n
    }
    return arr.length
}