这篇文章给大家分享的是有关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如何获取最长递增子序列”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
