We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
There was an error while loading. Please reload this page.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
给定一个无序的整数数组,找到其中最长上升子序列的长度。
示例:
输入: [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 = 0 ~ i
只要 i > j,就说明 [j, i] 可以形成一个上升子序列,那么只需要把已经求解好的 j 位置的最长上升序列的长度 dp[j] 拿出来 +1 即可得到 i 位置的最长上升序列长度。从 0 ~ j 循环找出其中和 i 形成的序列长度的最大值,记录在 dp[i] 位置即可。
i > j
[j, i]
j
dp[j]
0 ~ j
dp[i]
最后从 dp 数组中取出最大值,就是这个问题的解。
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) }
The text was updated successfully, but these errors were encountered:
No branches or pull requests
Uh oh!
There was an error while loading. Please reload this page.
给定一个无序的整数数组,找到其中最长上升子序列的长度。
示例:
可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
你算法的时间复杂度应该为 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
数组中取出最大值,就是这个问题的解。The text was updated successfully, but these errors were encountered: