Skip to main content

最长递增子序列

题目​

https://leetcode-cn.com/problems/longest-increasing-subsequence/description/

分析​

  1. 判断是哪种题目
  2. 确定是动态规划
    1. 明确 dp 数组是啥意思
    2. 确定 dp 的递推公式

dp[i] 指的是：数组前 i 个元素中，最长递增序列为多少？

dp[i] 的递推公式为：(nums[i] > nums[j]) && dp[i] = Math.max(dp[i], dp[j] + 1)

题解​

const lengthOfLIS = function(nums) {
  const len = nums.length
  // 1. fill的为 1
  const dp = Array(len).fill(1)
  // 2. 对nums中每个进行遍历
  for(let i = 0; i < len; i++) {
    // 3. 对当前变得的 i 之前的元素进行遍历
    for(let j = 0; j < i; j++) {
      // 4. 对nums[i] 和 i 之前的 nums[j] 进行大小比较
      if(nums[i] > nums[j]) {
        // 5. 取较大的那一个
        dp[i] = Math.max(dp[i], dp[j] + 1)
      }
      // (nums[i] > nums[j]) && (dp[i] = Math.max(dp[i], dp[j] + 1))
    }
  }
}