只要 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)
}
给定一个无序的整数数组,找到其中最长上升子序列的长度。
示例:
可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。 你算法的时间复杂度应该为 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
数组中取出最大值,就是这个问题的解。