leetcode673_go_最长递增子序列的个数题目给定一个未排序的整数数

题目给定一个未排序的整数数组，找到最长递增子序列的个数。
示例 1:输入: [1,3,5,4,7] 输出: 2
【leetcode673_go_最长递增子序列的个数】解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7] 。
示例 2:输入: [2,2,2,2,2] 输出: 5
解释: 最长递增子序列的长度是1 ，并且存在5个子序列的长度为1 ，因此输出5 。
注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。
解题思路分析1、动态规划；时间复杂度O(n^2) ，空间复杂度O(n)
文章插图
func findNumberOfLIS(nums []int) int { n := len(nums) if n == 0 || nums == nil {return 0 } dp := make([]int, n) count := make([]int, n) maxValue := 0 for i := 0; i < n; i++ {dp[i] = 1count[i] = 1for j := 0; j < i; j++ {if nums[j] < nums[i] {if dp[i] < dp[j]+1 {count[i] = count[j]} else if dp[i] == dp[j]+1 {count[i] = count[i] + count[j]}dp[i] = max(dp[j]+1, dp[i])}}maxValue = http://kandian.youth.cn/index/max(maxValue, dp[i]) } res := 0 for i := 0; i < n; i++ {if dp[i] == maxValue {res = res + count[i]} } return res}func max(a, b int) int { if a> b {return a } return b}总结Medium题目，题目意思同leetcode 300.最长上升子序列，额外借助一个数组存储个数