0673.md

Number of Longest Increasing Subsequence

题目

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.

总结    

    dp问题, 问题的结果依赖子问题的n个变量和n个中间结果。
    cache []int用来存储子问题的n个变量，使用nums[i]作为最后一个字符能构成有限个subsequence，最长的subsequence长度放在cache[i]中。
    count []int用来存储n个中间结果，使用nums[i]作为最后一个字符能构成有限个subsequence，最长的subsequence的数量放在count[i]中 。
    结果等于 count[x]+count[x1]...count[xn],其中x1..xn均满足cache[x1]..cache[xn]为cache中的最大值。

代码

func findNumberOfLIS(nums []int) int {
    if len(nums) <= 1 {
        return len(nums)
	}
	cache := make([]int, len(nums))
    max := 0
	count := make([]int, len(nums))
	for i := 0; i < len(nums); i++ {
        cache[i] = 1
		for j := i-1; j >= 0; j-- {
            if nums[i] > nums[j] && cache[j] >= cache[i] {
                cache[i] = cache[j] + 1
			}
		}
        for j := i-1; j >= 0;j-- {
            if nums[i] > nums[j] && cache[i] == cache[j] + 1 {
                count[i] += count[j]
            }
        }
        if count[i] == 0 {
            count[i] = 1
        }
        if max < cache[i] {
            max = cache[i]
        }
	}
    //fmt.Println(cache,count)
    res := 0
    for i := 0; i < len(nums); i++ {
        if cache[i] == max {
            res += count[i]
        }
    }
	return res
}