LeetCode: Number of Longest Increasing Subsequence Posted on June 18, 2019July 26, 2020 by braindenny Number of Longest Increasing Subsequence Similar Problems: CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #lis Given an unsorted array of integers, find the number of longest increasing subsequence. Example 1: Input: [1,3,5,4,7] Output: 2 Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7]. Example 2: Input: [2,2,2,2,2] Output: 5 Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5. Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int. Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. Solution: // https://code.dennyzhang.com/number-of-longest-increasing-subsequence // Basic Ideas: dynamic programming // dp(i): ends with nums[i] // Complexity: Time O(n*n), Space O(n) type Node struct { max int count int } func findNumberOfLIS(nums []int) int { res, max := 0, 0 l := make([]Node, len(nums)) for i, num := range nums { l[i].max, l[i].count = 1, 1 if i != 0 { for j:=i-1; j>=0; j-- { if nums[j] < num { if l[j].max+1 > l[i].max { l[i].max, l[i].count = l[j].max+1, l[j].count } else { if l[j].max+1 == l[i].max { l[i].count += l[j].count } } } } } if l[i].max > max { max, res = l[i].max, l[i].count } else { if l[i].max == max { res += l[i].count } } } return res } Post Views: 0