Commit7e081dc

committed

feat: add no.300

1 parentf5e3270 commit7e081dcCopy full SHA for 7e081dc

File tree

+44

-0

lines changed

+44

-0

lines changed

Lines changed: 44 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,44 @@`
	`1`	`+/**`
	`2`	`+ * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。`
	`3`	`+`
	`4`	`+子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的`
	`5`	`+子序列`
	`6`	`+。`
	`7`	`+`
	`8`	`+`
	`9`	`+示例 1：`
	`10`	`+`
	`11`	`+输入：nums = [10,9,2,5,3,7,101,18]`
	`12`	`+输出：4`
	`13`	`+解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。`
	`14`	`+示例 2：`
	`15`	`+`
	`16`	`+输入：nums = [0,1,0,3,2,3]`
	`17`	`+输出：4`
	`18`	`+示例 3：`
	`19`	`+`
	`20`	`+输入：nums = [7,7,7,7,7,7,7]`
	`21`	`+输出：1`
	`22`	`+`
	`23`	`+ * 动态规划`
	`24`	`+ * dp 定义：记录以坐标 i 结尾的最长递增子序列长度`
	`25`	`+ * 状态转移方程：dp[i] = Math.max(dp[j]+1, dp[i])`
	`26`	`+ * 以 i 结尾的最长子序列长度，所有 i 结尾的最长子序列长度的最大值，就是最长子序列长度`
	`27`	`+ *@param {number[]} nums`
	`28`	`+ *@return {number}`
	`29`	`+ */`
	`30`	`+varlengthOfLIS=function(nums){`
	`31`	`+letdp=newArray(nums.length).fill(1);`
	`32`	`+letresult=1;`
	`33`	`+`
	`34`	`+for(leti=1;i<nums.length;i++){`
	`35`	`+for(letj=0;j<i;j++){`
	`36`	`+if(nums[j]<nums[i]){`
	`37`	`+dp[i]=Math.max(dp[j]+1,dp[i])`
	`38`	`+}`
	`39`	`+}`
	`40`	`+result=Math.max(result,dp[i]);`
	`41`	`+}`
	`42`	`+`
	`43`	`+returnresult;`
	`44`	`+};`

Comments

(0)