leetcode-go/leetcode/medium/673.number-of-longest-increasing-subsequence.go

func findNumberOfLIS(nums []int) int {
	n, max := len(nums), 1
	if n == 0 {
		return 0
	}
	dp := make([]int, n)     // The number of LIS end with nums[i]
	length := make([]int, n) // The length of LIS ...
	dp[0], length[0] = 1, 1
	for i := 1; i < n; i++ {
		dp[i], length[i] = 1, 1
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				if l := length[j] + 1; l == length[i] {
					dp[i] += dp[j]
				} else if length[i] < l {
					if max < l {
						max = l
					}
					dp[i] = dp[j]
					length[i] = l
				}
			}
		}
	}
	res := 0
	for i := range dp {
		if length[i] == max {
			res += dp[i]
		}
	}
	return res
}