31 lines
677 B
JavaScript
31 lines
677 B
JavaScript
/**
|
||
* @param {number[]} nums
|
||
* @return {number}
|
||
*/
|
||
const lengthOfLIS = function (nums) {
|
||
|
||
};
|
||
|
||
/*
|
||
设dp[i]为以nums[i]结尾的递增子序列的最长长度,那么dp[i]，nums[i]可以接在nums[0-i)中比它小的元素
|
||
组成子序列，求那个结果最长的就是dp[i],即dp[i] = Max(nums[0-i)) +1
|
||
*/
|
||
function f1(nums) {
|
||
const n = nums.length;
|
||
const dp = Array(n).fill(1);
|
||
dp[0] = 1;
|
||
for (let i = 1; i < n; i++) {
|
||
for (let j = 0; j < i; j++) {
|
||
if (nums[j] < nums[i]) {
|
||
// 更新dp[i]为最长子序列
|
||
dp[i] = Math.max(dp[j] + 1, dp[i]);
|
||
}
|
||
}
|
||
}
|
||
console.log(dp);
|
||
|
||
return dp[n - 1];
|
||
}
|
||
|
||
f1([1, 3, 6, 7, 9, 4, 10, 5, 6]);
|