最长递增子序列(⭐⭐)

leetcode

题目

输入一个无序的整数数组，请你找到其中最长递增子序列的长度。

例如：输入nums = [10, 9, 2, 5, 3, 7, 101, 18]，其中最长的递增子序列是[2, 3, 7, 101]，所以输出4

思路：动态规划

• 定义dp[i]表示以nums[i]这个数结尾的最长递增子序列长度
• base case: dp[i]初始值为1
• dp[i]的值等于 在前n-1个中第j个 递增子序列长度 + 1，j要满足要满足nums[i] > nums[j]，存在多种情况，取最大值
• dp数组中的最大值就是整个nums最长递增子序列的长度

解法

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
    // dp[i]表示以nums[i]这个数结尾的最长递增子序列长度，初始化为1
    const dp = new Array(nums.length).fill(1)
    for (let i = 0; i < nums.length; i ++) {
        for (let j = 0; j < i; j++) {
            // dp[i] 的值等于第j个递增子序列长度 + 1(j要满足nums[i] > nums[j])
            // 存在多种情况，取最大值
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
    }
    return Math.max(...dp)
};