300 最长递增子序列.md

300 最长递增子序列

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

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

 

示例 1：

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

示例 2：

**输入：**nums = [0,1,0,3,2,3] **输出：**4

示例 3：

**输入：**nums = [7,7,7,7,7,7,7] **输出：**1

动态规划 记忆化搜索 从后往前找 找到比后一个数小的最大的那个

var lengthOfLIS = function(nums) {
    const memo = [];

    function dfs(i) {
        if (memo[i] !== undefined) return memo[i]; // 检查是否已缓存
        let res = 0;
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                res = Math.max(res, dfs(j));
            }
        }
        const result = res + 1;
        memo[i] = result; // 存储到数组
        return result;
    }

    let maxLen = 0;
    for (let i = 0; i < nums.length; i++) {
        maxLen = Math.max(maxLen, dfs(i));
    }
    return maxLen;
};

改成递推

function lengthOfLIS(nums) {
    if (nums.length === 0) return 0;
    const f = new Array(nums.length).fill(0); // 初始化f数组
    
    for (let i = 0; i < nums.length; i++) {
        // 初始时，最长递增子序列至少包含自己（长度为1）
        f[i] = 1; // 直接初始化为1（替代原来的+=1）
        // 检查所有前面的元素
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                f[i] = Math.max(f[i], f[j] + 1); // 更新最大值
            }
        }
    }
    return Math.max(...f); // 取f数组中的最大值
}

贪心+二分 维护一个数组单调递增数组g 每次遍历出的东西往g里加 定义 g[i] 表示长为 i+1 的上升子序列的末尾元素的最小值。 一次只能添加或修改一个值 添加就是比最末尾大 加到最末尾 修改就是比最末尾小 查找比他小的最大值 修改那个放进去 过程中的g不是答案 之后过程结束才是答案

function lengthOfLIS(nums) {
    const g = [];
    
    // 实现 bisect_left 等效功能
    const bisectLeft = (arr, target) => {
        let low = 0;
        let high = arr.length;
        while (low < high) {
            const mid = (low + high) >>> 1; // 无符号右移等价于 Math.floor((low + high)/2)
            if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    };

    for (const x of nums) {
        const j = bisectLeft(g, x);
        if (j === g.length) { // 当x是当前最大元素时
            g.push(x);
        } else {
            g[j] = x;
        }
    }
    return g.length;
}