673. 最长递增子序列的个数、Leetcode的Go实现

673. 最长递增子序列的个数、Leetcode的Go实现

​​673. 最长递增子序列的个数​​

给定一个未排序的整数数组，找到最长递增子序列的个数。

示例 1:

输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:

输入: [2,2,2,2,2] 输出: 5 解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。

属于​​300. 最长递增子序列、Leetcode的Go实现_李歘歘的博客-CSDN博客​​的进阶版本：

动态规划

分为两步

计算到每一个元素为止，最长的严格递增子序列长度，存放到数组num中，最长的严格递增子序列长度出现的次数存放到数组count中。从数组num中找出最大值，在count中找最大值对应count中出现的次数，相加即为结果。

关于第一步，我们使用动态规划：

我们在计算到第i个元素为止的最长的严格递增子序列时，已经知道了到前i-1个元素为止的最长的严格递增子序列。所以可以走以下两步骤：

只需要按顺序遍历比较前i-1个元素nums[j]和当前元素nums[i]的大小，当nums[j]

func findNumberOfLIS(nums []int) int { num := make([]int,len(nums)) // 存放到当前元素为止，最长递增子序列元素个数 count:= make([]int,len(nums)) // 存放到当前元素为止，最长递增子序列元素个数出现的次数 for i:=0;i=num[i]{ // 临时元素的递增子序列元素个数大于等于当前元素递增子序列元素个数(确保遍历前i-i个元素完成后当前元素的递增子序列元素个数为最大，大的值会覆盖小的值) num[i]=num[j]+1 // 给到当前元素为止的递增子序列元素赋值 count[i] = count[j] }else if num[i]==num[j]+1 { // 当最长递增子序列元素个数再次出现 count[i] = count[i]+count[j] // 将出现次数累加即可，想一想排列组合 } } } } max := 0 for i:=0;i

当然也可以将找最大值的那一步与步骤一进行合并，在遍历的过程中就记录下最大值，将第二步省略：

func findNumberOfLIS(nums []int) int { num := make([]int,len(nums)) // 存放到当前元素为止，最长递增子序列元素个数 count:= make([]int,len(nums)) // 存放到当前元素为止，最长递增子序列元素个数出现的次数 max := 1 for i:=0;i=num[i]{ // 临时元素的递增子序列元素个数大于等于当前元素递增子序列元素个数(确保遍历前i-i个元素完成后当前元素的递增子序列元素个数为最大，大的值会覆盖小的值) num[i]=num[j]+1 // 给到当前元素为止的递增子序列元素赋值 if max < num[i] { // 计算最长递增子序列元素个数 max = num[i] } count[i] = count[j] }else if num[i]==num[j]+1 { // 当最长递增子序列元素个数再次出现 count[i] = count[i]+count[j] // 将出现次数累加即可，想一想排列组合 } } } } res := 0 for i := 0; i < len(count); i++ { if num[i] == max { // 最长递增子序列元素个数若为最大值 res = res + count[i] // 将最大值对应的出现次数相加 } } return res}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。