On this page

最长递增子序列

TIP

给你一个整数数组nums，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，**删除（或不删除）**数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

思路

dp[i]表示：以下标为i的元素结尾的子序列最大长度
初始化：dp[0] = 1

js

var lengthOfLIS = function(nums) {
   let dp = Array(nums.length).fill(1)	//全部初始化为 1
   for(let i=1;i<nums.length;i++){		
      for(let j=0;j<i;j++){				//遍历 i 之前的所有数，判断是否有比 nums[i] 小的
          if(nums[i]>nums[j]) dp[i] = Math.max(dp[j]+1,dp[i])
      }
   }
   console.log(dp)
   return Math.max(...dp)
};