题目描述
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
我的AC代码
var lengthOfLIS = function(nums) {
if(nums.length === 0) return 0;
let dp = new Array(nums.length);
dp[0] = 1;
let res = 1;
for (let i = 1; i < nums.length; i++) {
let tempMaxLen = 0;
for(let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
tempMaxLen = Math.max(dp[j], tempMaxLen);
}
}
dp[i] = tempMaxLen + 1;
res = Math.max(dp[i], res);
}
return res;
}
题解思路
此题为典型的动态规划问题。 我们定义dp[i]为以i结尾的最长上升子序列的长度。 那么0在i-1的范围中，假如nums[i]能够连接上左边的最长上升子序列，那么需要满足nums[i] > nums[j]
