力扣300题-最长递增子序列

题目

看到题目，我想的就是用dfs，回溯，但是真的离谱，一半多都超时了，代码如下。

var lengthOfLIS = function(nums) {
    return dfs(nums, 0, -Infinity, 0);
};

function dfs(nums, all, last, idx){
    if(idx>=nums.length)return all;
    const right = dfs(nums, all, last, idx+1);
    if(nums[idx]<=last)return right;
    return Math.max(dfs(nums,all+1,nums[idx],idx+1), right);
}

实在想不出来别的方法了，看了看题解

var lengthOfLIS = function(nums) {
    if(nums.length===0)return 0;
    let dp = new Array(nums.length);
    dp[0] = 1;
    let max = 1;
    for(let i=1;i<nums.length;i++){
        dp[i] = 1;
        for(let j=0;j<i;j++){
            if(nums[i]>nums[j])
            dp[i] = Math.max(dp[i],dp[j]+1);
        }
        max = Math.max(max,dp[i]);
    }
    return max;
};