300. 最长递增子序列 JavaScript实现

300. 最长递增子序列

题目链接
题目详解

一、思想 – 动态规划

1、dp[i] 是指从0位置到i位置，并且以i位置结尾的序列的最长递增子序列的长度

2、状态转移方程
假设我们已经知道了 dp[0…4] 的所有结果，我们如何通过这些已知结果推出 dp[5] 呢？
nums[5] = 3，既然是递增子序列，我们只要找到前面那些结尾比 3 小的子序列，然后把 3 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。

二、代码实现

var lengthOfLIS = function(nums) {
    // dp[i]表示以i位置结尾的最长递增子序列的长度，初始化的时候，长度均为为1，即本身。
    const dp = new Array(nums.length).fill(1);
    
    // 遍历数组，对于每个位置都要去寻找最长递增子序列
    for(let i=0; i<nums.length; i++){
        // 向前找比i小的数字
        for(let j=0;j<i;j++){
            // 找到之后，就和原来的长度1进行比较。如果比1长就长度+1.否则不变
            if(nums[i]>nums[j]){
                // 更新数组的值
                dp[i] = Math.max(dp[i],dp[j]+1);
            }
        }
    }
    return Math.max(...dp);  
};