题解 | #最长上升子序列(一)#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 给定数组的最长严格上升子序列的长度。
 * @param arr int整型一维数组 给定的数组
 * @return int整型
 核心思路：当遍历的数字大于tails最后一项末尾数字时，新增记录 else: 找tails数组中第一个末尾大于该数字的记录,更改其末尾
 */
function LIS( arr ) {
    if(arr.length === 0) return 0
    const tails = [arr[0]]
    for(let i = 1; i < arr.length; i++) {
        if(arr[i] > tails[tails.length - 1]) {
            tails.push(arr[i])
        }
        else {
            const index = getFirstGreateIndex(arr[i])
            tails[index] = arr[i]
        }
    }
    function getFirstGreateIndex(target) {
        // 二分查找
        let i = 0; j = tails.length - 1
        while(i < j) {
            const mid = Math.floor((i + j) / 2)
            if(tails[mid] >= target) {
                j = mid
            }
            else {
                i = mid + 1
            }
        }
        return i
    }
    return tails.length
}
module.exports = {
    LIS : LIS
};