300. Longest Increasing Subsequence

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @return {number}
 */

题目给我们一个数字数组 nums

要求我们返回 nums 中能组成最长升序数组的元素个数

解题思路

我们可以用一个数组 dp 来保存最长的升序数组元素个数（dp[i] 代表 nums[0..i] 最长的升序数组元素个数）

我们要针对 nums 中的每一个元素 num 来更新 dp 数组的对应值

具体来说，当遍历到 nums[i] 时，我们需要找出 nums[0...i] 中小于 nums[i] 且对应 dp 最大的值+1 赋值给 dp[i]

最后，我们要在 dp 数组中找到最大值返回

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
    const len = nums.length
    // dp[i]: record longest increasing subsequence's length from nums[0] to nums[i]
    const dp = new Array(len).fill(1)

    for (let i = 1; 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)
};