题解 | #最长递增子序列#

function LIS( arr ) {
    /** 动态规划 */
    // 状态：dp[i]表示以第i个元素结尾的递增子序列；
    // 状态转移：dp[i] = max{dp[0, i-1]}
    // 计算最dp[i];
    // 反向遍历寻找元素；

    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 = max > dp[i] ? max : dp[i];
            }
        }
    }

    console.log('max', max)

    const res = new Array(max);
    for (let i= dp.length-1, j=max; j>0; i--) {
        if (dp[i] === j) {
            j--
            res[j] = arr[i]
        }
    }

    return res;

}
module.exports = {
    LIS : LIS
};