最长递增子序列算法 | Coding Your Life

最长递增子序列（Longest Increasing Subsequence，LIS）是一个经典的动态规划问题，目标是在给定数组中找到一个最长的严格递增子序列（元素可以不连续）。以下从算法原理到优化实现进行详细解析：

一、问题定义

给定一个无序的整数数组 nums，找到其中最长严格递增子序列的长度。

1
2
3

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，长度为4。

二、动态规划解法（基础）

核心思路

状态定义：dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
状态转移：对于每个 i，遍历其前面的所有元素 j（0 ≤ j < i），如果 nums[j] < nums[i]，则 dp[i] = max(dp[i], dp[j] + 1)。
初始状态：每个元素自身构成一个长度为1的子序列，故 dp[i] = 1。

代码实现

// 最长递增子序列暴力算法
function lengthOfLIS(nums: number[]){
    if(!nums.length) return;
    const len = nums.length;
    const dp = Array(len).fill(1)  // 初始化dp数组
    for(let i = 0; i < len; i++){
        for(let j = 0; j < i; j++){
            if(nums[j] < nums[i]){
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return Math.max(...dp)  // 返回最大值
} 
// 但是上面的算法子能获取最长递增子序列的长度，但是不能返回最长递增子序列。下面改造一下：

function lengthOfLIS(nums: number[]){
    if(!nums.length) return;
    const len = nums.length;
    const dp = Array(len).fill(1)  // 初始化dp数组
    const preNode = Array(len).fill(-1);    // 记录每个位置的递增子序列的前一个节点
    let maxLen = 1, lastIndex = 0;  // 最长递增子序列的长度，以及最长递增子序列的最后一个节点的索引
    for(let i = 0; i < len; i++){
        for(let j = 0; j < i; j++){
            if(nums[j] < nums[i] && dp[i] <= dp[j] + 1){
                dp[i] = dp[j] + 1;
                preNode[i] = j;
            }
        }
        if(dp[i]> maxLen){
            maxLen = dp[i];
            lastIndex = i;
        }
    }
    const res: number[] = [];
    while(lastIndex !== -1){
        res.push(nums[lastIndex]);
        lastIndex = preNode[lastIndex];
    }
    return res.reverse();  // 返回最大值
}

复杂度分析

时间复杂度：$O(n^2)$，需要两层循环。
空间复杂度：$O(n)$，用于存储 dp 数组。

三、贪心 + 二分查找（优化解法）

核心思路

维护一个数组 tails：其中 tails[k] 表示长度为 k+1 的递增子序列的末尾最小元素。
遍历数组：对于每个元素 num，通过二分查找找到其在 tails 中的插入位置：
- 如果 num 大于所有 tails 中的元素，直接添加到末尾，形成更长的子序列。
- 否则，替换第一个大于等于 num 的元素，保持 tails 的最小性。

代码实现

function lengthOfLIS(nums: number[]){
    const tails: number[] = []  // 维护当前最长递增子序列的末尾元素
    const len = nums.length
    // 记录节点的前一个节点
    const preNode: number[] = Array(len).fill(-1);
    // 记录当前节点的索引
    const preIndex: number[] = [];
    for(let i = 0; i < len; i++){
        let left = 0; 
        let right = tails.length;
        // 二分查找插入位置, 找到第一个大于等于nums[i]的索引
        // left <= right 此时非严格递增，如果有相等的数字会累计， left < right为严格递增，相等的数字只会统计一次
        while (left < right){   
            // 中间位置索引
            const mid = Math.floor((left + right) / 2)
         
            if(tails[mid] < nums[i]){
                left = mid + 1
            }else{
                right = mid
            }
        }
        // 插入或替换元素
        if (left === tails.length){
            tails.push(nums[i])  // 形成更长的子序列
        }else{
            tails[left] = nums[i]  // 替换为更小的末尾元素
           
        }
        // 下面两行代码的执行顺序很重要，如果是非严格递增，
        // 必须先记录前一个节点的索引再更新节点索引，否则后续会死循环
        preNode[i] = tails[left-1] ? preIndex[tails[left-1]]:-1
        preIndex[nums[i]] = i
    }
    // 回溯序列的元素,得到最长递增子序列
    const lastItem = tails[tails.length-1];
    const res = [lastItem];
    const index = preIndex[lastItem];
    let node = preNode[index];
    while(node !== -1){
        res.push(nums[node]);
        node = preNode[node]
    }
    // res  为LIS序列
    // return res.reverse();
    // tails 记录LIS的长度， 思考🤔️：tails数组为啥不能直接作为最长递增子序列?
    return tails.length 
}

复杂度分析

时间复杂度：$O(n \log n)$，每次二分查找耗时 $O(\log n)$。
空间复杂度：$O(n)$，主要用于存储 tails 数组。

四、关键差异对比

方法	时间复杂度	空间复杂度	适用场景
动态规划	$O(n^2)$	$O(n)$	数据规模较小（n ≤ 1000）
贪心 + 二分查找	$O(n \log n)$	$O(n)$	数据规模较大（n > 1000）

五、总结

动态规划：适用于小规模数据，代码简单易理解。
贪心 + 二分查找：适用于大规模数据，性能更优，但逻辑较复杂。
应用场景：涉及最长递增子序列的问题（如版本控制、序列比对等）。

掌握这两种解法，能应对大多数 LIS 相关问题，并可根据数据规模选择最优方案。