leetcode如何获取最长递增子序列

这篇文章给大家分享的是有关leetcode如何获取最长递增子序列的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。

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

示例 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位有符号整数。

1,定义l[i]存储,以nums[i]结尾的最长递增子序列长度,c[i]为个数

2,则初始化条件为:l[0:len(nums)]=1  c[0:len(nums)=1]

3,对于任意j<i,如果nums[j]<nums[i](注意严格递增),则l[i]=max(l[i],l[j]+1)

4,如果nums[j]<nums[i] 且l[i]==l[j+1] 则c[i]=c[i]+1

5,找出l[i]==max(l[i]),的下标,把对应c值个数加起来就是答案(补充nums[i]==nums[j]的情况)

func findNumberOfLIS(nums []int) int {  if len(nums) < 1 {    return 0  }  l := make([]int, len(nums))  c := make([]int, len(nums))  max := 0  for i := 0; i < len(nums); i++ {    l[i] = 1    c[i] = 1  }  for i := 1; i < len(nums); i++ {    for j := 0; j < i; j++ {      if nums[j] < nums[i] {        if l[i] < l[j]+1 {          l[i] = l[j] + 1          c[i] = c[j]        } else if l[i] == l[j]+1 {          c[i] = c[j] + 1        }      }    }    if max < l[i] {      max = l[i]    }  }  sum := 0  for i := 0; i < len(nums); i++ {    if l[i] == max {      sum += c[i]    }  }  return sum}

感谢各位的阅读!关于“leetcode如何获取最长递增子序列”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!

原创文章,作者:745907710,如若转载,请注明出处:https://blog.ytso.com/224043.html

(0)
上一篇 2022年1月7日
下一篇 2022年1月7日

相关推荐

发表回复

登录后才能评论