SOURCE

/**
 * 最长递增子序列 LIS 动态规划解法 O(n²)
 * dp[i] 定义：以 arr[i] 作为结尾元素的最长递增子序列长度
 * @param {number[]} arr - 目标数组
 * @returns {number} 最长递增子序列元素
 */
function lengthOfLIS(arr) {
    const len = arr.length
    // 边界：空数组直接返回0
    if(len <= 1) return arr
    // dp数组初始化：每个元素自身构成长度为1的子序列
    const dp = new Array(len).fill(1)
    // 记录全局最大长度，初始最小为1
    let maxlen = 1
    // 保存最长序列末尾元素下标
    let lastIndex = 0
    // 记录前驱索引，prevs[i] = j 代表最优路径上i的前一个节点是j
    const prevs = new Array(len).fill(-1)
    for(let i = 1; i < arr.length; i++) {
        // j 遍历i前面所有元素，尝试接在j后面形成更长序列
        for(let j = 0; j < i; j++) {
            // arr[j] < arr[i] 满足递增条件
            // dp[j] + 1 > dp[i] 说明可以更新为更长的子序列
            if (arr[j] < arr[i] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1
                prevs[i] = j
            }
        }
        // 更新全局最长长度
        if (maxlen < dp[i]) {
            maxlen = dp[i]
            lastIndex = i
        }
    }
    // 逆向回溯前驱列表
    const res = []
    let cur = lastIndex
    while(cur !== -1) {
        res.unshift(arr[cur])
        cur = prevs[cur]
    }
    // console.log(prevs)
    // return [...new Set(prevs.filter(i => i !== -1))]
    //     .reduce((total, item) => {
    //         total.push(arr[item])
    //         return total
    //     }, [])
    return res
}
console.log(lengthOfLIS([2, 1, 6, 3, 4]))