题解 | #最小编辑代价#

/**
 * retrun the longest increasing subsequence
 * @param arr int整型一维数组 the array
 * @return int整型一维数组
 */
function LIS( arr ) {
    // write code here
    // 贪心+二分
    // 自顶向下编程
    function search(arr, target) {
        let pos = -1; 
        let left = 0, right = arr.length-1;
        let mid;
        
        while (left<=right) {
            mid = Math.floor(left + (right-left)/2)
            if (arr[mid] >= target) {
                right = mid-1
            } else {
                left = mid+1
            }
        }
        return left
    }
    
    let dp = [arr[0]];
    let len = [1]
    for (let i=1; i<arr.length; i++) {
        if (arr[i] > dp[dp.length-1]) {
            dp.push(arr[i])
            len.push(dp.length)
        } else {
            let k = search(dp, arr[i]);
            dp[k] = arr[i]
            len.push(k+1)
        }
    }
    let max = dp.length;
    let res = []
    for (let i=len.length-1, j=max; j>0; i--) {
        if (len[i] === j) {
            j--
            res[j] = arr[i]
        }
    }
    return res
    
    
}
module.exports = {
    LIS : LIS
};