最长上升子序列(三)

简单版本得到序列

我们知道通过贪心+二分可以求出最长递增子序列的长度，但由于每次更新len长度序列的结尾元素，导致了dp数组是真，结果不是最长的递增子序列，只能保证最长递增子序列的结尾元素。既然知道了失真的原因，那么就可以另外建立一个数组，在每次失真操作前保存序列。
具体：

• 当更新dp最后一个元素时，应该保存dp数组，此时数组是当前最大长度的未失真序列。
• 当dp数组长度增加时，应该在res数组后加上此元素，res.push(arr[i])

function LIS( arr ) {
    const dp = [];
    let res = [];
    for (let i=0; i<arr.length; ++i) {
        let r = dp.length-1, l = 0;
        let pos = dp.length;
        while(l <= r) {
            const mid = Math.floor((r - l) / 2) + l; 
            if (dp[mid] >= arr[i]) {
                r = mid-1;
                pos=mid;
            } else if (dp[mid] < arr[i]){
                l = mid+1;
            }
        }
        // 获得递增序列
        if(pos===dp.length) {
            res.push(arr[i]);
        } else if (pos === dp.length-1) {
            res[res.length-1] = arr[i];
        }
        dp[pos] = arr[i];
    }
    return res;
}

超时版：

function LIS( arr ) {
    if (arr === null || arr.length === 0) return 0;
    const dp = new Array(arr.length).fill(1);
    let max = 1;
    for (let i = 1; i < arr.length; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
                max = Math.max(max, dp[i]);
            }
        }
    }
    const result = new Array(max);
    for (let i = dp.length - 1; i >= 0; i--) {
        if (dp[i] === max) result[--max] = arr[i];
    }
    return result;
}

通过版：

function LIS( arr ) {
    const list = new Array(arr.length + 1);
    const maxLen = new Array(arr.length);
    let n = 1;
    list[1] = arr[0];
    maxLen[0] = 1;
    for (let i = 0; i < arr.length; i++) {
        if (list[n] < arr[i]) {
            list[++n] = arr[i];
            maxLen[i] = n;
        } else {
            const index = binarySearch(list, n, arr[i]);
            list[index] = arr[i];
            maxLen[i] = index;
        }
    }
    const result = new Array(n);
    for (let i = maxLen.length - 1; i >= 0; i--) {
        if (maxLen[i] === n) result[--n] = arr[i];
    }
    return result;
}
function binarySearch(arr, right, key) {
    let left = 0;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] >= key) right = mid - 1;
        else left = mid + 1;
    }
    return left;
}