最长上升子序列-300

[sl1673495]

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

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

思路

从前往后求解，对于每个值 i，都需要从 j = 0 ~ i 依次求解。

只要 i > j，就说明 [j, i] 可以形成一个上升子序列，那么只需要把已经求解好的 j 位置的最长上升序列的长度 dp[j] 拿出来 +1 即可得到 i 位置的最长上升序列长度。从 0 ~ j 循环找出其中和 i 形成的序列长度的最大值，记录在 dp[i] 位置即可。

最后从 dp 数组中取出最大值，就是这个问题的解。

/**
 * @param {number[]} nums
 * @return {number}
 */
let lengthOfLIS = function (nums) {
  let dp = []
  let n = nums.length
  if (!n) {
    return 0
  }

  dp[0] = 1
  for (let i = 1; i < n; i++) {
    let num = nums[i]
    let max = 1
    // j 从 [0, i) 依次求出可以和 i 组成的最长上升子序列
    for (let j = 0; j < i; j++) {
      let prevNum = nums[j]
      if (num > prevNum) {
        // 循环中不断更新 max 值
        max = Math.max(max, dp[j] + 1)
      }
    }
    dp[i] = max
  }

  return Math.max(...dp)
}