2022.04.22-第90题-673. 最长递增子序列的个数

[icodeish]

https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/ 给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。 注意 这个数列必须是 严格 递增的。 示例 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。

[icodeish]

var findNumberOfLIS = function(nums) {
    let len = nums.length;
    if(len <= 1) return len;
    let length = new Array(len).fill(0), counts = new Array(len).fill(1);
    for (let j = 0; j < len; j++) {
        for (let i = 0; i < j; i++) {
            if(nums[i] < nums[j]){
                if(length[i] >= length[j]) {
                    length[j] = length[i] + 1;
                    counts[j] = counts[i];
                } else if(length[i] + 1 === length[j]) {
                    counts[j] += counts[i]
                }
            }
        }
    }
    let longest = 0, ans = 0;
    for (let i = 0; i < length.length; i++) {
        longest = Math.max(longest, length[i]);
    }
    for (let j = 0; j < len; j++) {
        if(length[j] === longest) {
            ans += counts[j]
        }
    }
    return ans;
};