给定一个无序的整数数组,编写js函数找到其中最长上升子序列的长度。
时间: 2023-05-20 13:00:40 浏览: 114
可以使用动态规划来解决这个问题。定义一个数组dp,其中dp[i]表示以第i个元素为结尾的最长上升子序列的长度。初始时,dp数组中的每个元素都为1,因为每个元素本身都可以作为一个长度为1的上升子序列。然后,从第二个元素开始遍历整个数组,对于每个元素,再从第一个元素开始遍历到当前元素,如果发现有比当前元素小的元素,就更新dp数组中的值,即dp[i] = Math.max(dp[i], dp[j] + 1),其中j表示比当前元素小的元素的下标。最终,dp数组中的最大值即为最长上升子序列的长度。
以下是完整的js代码:
function findLongestIncreasingSubsequenceLength(nums) {
if (!nums || nums.length === 0) {
return 0;
}
const dp = new Array(nums.length).fill(1);
let maxLength = 1;
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
}
console.log(findLongestIncreasingSubsequenceLength([10, 9, 2, 5, 3, 7, 101, 18])); // 4
阅读全文