SOURCE

// 思路
// 因为是记录不一定连续的递增子序列 因此依赖于之前递增子序列长度
// 来得到起始位置到当前位置所构成的子序列长度
// 并记录最大长度 以此判断是否更新 最长子序列末尾索引
// 通过构建类似KMP next数组 记录子序列每个数的前一位索引
// 最后通过该索引数组 找到符合的子序列

function fn(nums) {
    if (nums.length < 2) return []
    // 记录历史长度 子序列最少为1个数 所以最小长度为1
    // 初始值先全部填充成1
    let max_lengths = new Array(nums.length).fill(1)
    // 记录nums每个位置的最长递增子序列的前一个元素的索引
    // 初始值-1用来作判断条件 不能用0 因为0位置的元素也可能在子序列中
    let pre_indexs = new Array(nums.length).fill(-1)

    let max = 1 // 记录nums最大子序列长度 最小为1
    let end_index // 最长子序列末尾索引

    // 子序列最小长度是1 从nums第二个元素开始遍历
    for (let fast = 1; fast < nums.length; fast++) {
        // 外层循环每移动到一个新位置 相当于从0到fast的滑动窗口
        // 里层遍历滑动窗口内元素 找到最大递增子序列长度
        // 并记录fast位置 构成的子序列 前一个数的索引位置
        // 只遍历到fast前一个位置 因为fast不需要跟自己作比较
        for (let slow = 0; slow < fast; slow++) {
            if (nums[slow] < nums[fast]) {
                // slow位置的数小于fast时
                // 说明新加入的fast使得0~slow子序列长度+1
                // 因此在max_lengths[slow]的基础上+1 得到新值
                // 然后比较max_lengths[fast]当前值 和 新值 得到0~fast区间最大子序列长度
                max_lengths[fast] = Math.max(max_lengths[slow] + 1, max_lengths[fast])
                // 并记录以fast为末尾的子序列 其前一个数位置
                pre_indexs[fast] = slow
            }
        }
        // 更新最大子序列长度
        if (max_lengths[fast] > max) {
            max = max_lengths[fast]
            // 注意区分 0~fast区间的最长子序列 和 nums的最长子序列
            // for循环中是以加入fast为前提 是否会增加子序列长度
            // 如果增加 说明0~fast区间的最长子序列 就是以fast为末尾
            // 而nums的最长子序列 末尾元素索引 不一定是nums末尾元素
            end_index = fast
        }
    }
    let result = []
    // 根据pre_indexs 从后往前找最长子序列
    while (end_index !== -1) {
        result.unshift(nums[end_index])
        // 移动end_index
        end_index = pre_indexs[end_index] // 是不是很像KMP的next数组？
    }
    return result
}

// 验证  
const nums = [10, 9, 2, 5, 3, 7, 101, 18];
console.log(`最长子序列:` + fn(nums)); // [2,3,7,101]