300. 最长递增子序列 (opens new window)

Description

Difficulty: 中等

Related Topics: 数组 (opens new window), 二分查找 (opens new window), 动态规划 (opens new window)

给你一个整数数组 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

提示：

• 1 <= nums.length <= 2500
• -10⁴ <= nums[i] <= 10⁴

进阶：

• 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

Solution

Language: JavaScript

动态规划

var lengthOfLIS = function(nums) {
    var ans = []; 
    for (var i = 0; i < nums.length; i++) {
        var left = 0, right = ans.length;
        while (left < right) { //二分法
            var mid = left + right >>> 1;
            if (ans[mid] < nums[i]) left = mid + 1;
            else right = mid;
        } 
        if (right >= ans.length) ans.push(nums[i]); //如果找不到 在ans最后增加一项nums[i]
        else ans[right] = nums[i];
    }
    return ans.length;
};

方法1.动态规划

思路：dp[i]表示选择nums[i]，并且以nums[i]结尾的最长上升子序列的长度。两层循环，i：1～nums.length，

j：0～i，如果nums[i] > nums[j]，则构成一个上升对，dp[i]就从dp[i], dp[j]+1两个种选择较大者，最后返回dp数组总的最大数

复杂度分析：时间复杂度O(n^2)，n是nums的长度，外层需要循环n次，dp[i]需要从dp[0~i-1],所以复杂度是O(n^2)。空间复杂度是O(n)，即dp数组的空间

/**
 * @param {number[]} nums
 * @return {number}
 */
const lengthOfLIS = (nums) => {
    let dp = Array(nums.length).fill(1);
    let result = 1;

    for(let i = 1; i < nums.length; i++) {
        for(let j = 0; j < i; j++) {
            if(nums[i] > nums[j]) {//当nums[i] > nums[j]，则构成一个上升对
                dp[i] = Math.max(dp[i], dp[j]+1);//更新dp[i]
            }
        }
        result = Math.max(result, dp[i]);//更新结果
    }

    return result;
};

解法1：动态规划。不同于解二维护的是一个二维数组memory，这里维护一个一维数组bp。bp[i]表示以第i个元素结尾的最长子序列长度。

var lengthOfLIS = function(nums) {
    var dp = new Array(nums.length).fill(1);
    var ans = 0;
    for (var i=0; i<nums.length;i++){ //对于第i个元素nums[i]
        for (var j=0; j<i;j++){ //遍历i前面的i-1个元素
            if (nums[j]<nums[i]) dp[i] = Math.max(dp[i],dp[j]+1)
            //如果nums[j]比nums[i]小 更新dp[i]
        }
        ans = Math.max(ans,dp[i]);
    }
    return ans
};