LeetCode：673. Number of longest increasing subsequences

Given an array of unsorted integers nums , Returns the number of longest increasing subsequences .

Be careful This sequence must be Strictly Incremental .

Example 1:

 Input : [1,3,5,4,7]
 Output : 2
 explain :  There are two longest increasing subsequences , Namely  [1, 3, 4, 7]  and [1, 3, 5, 7].

Example 2:

 Input : [2,2,2,2,2]
 Output : 5
 explain :  The length of the longest increasing subsequence is 1, And it exists 5 The length of the subsequence is 1, So output 5.

Tips :

• 1 <= nums.length <= 2000
• -10^6 <= nums[i] <= 10^6

---

Their thinking

1. First initialize two arrays ： state dp[i] Said to nums[i] The length of the longest ascending subsequence at the end ,count[i] Said to nums[i] Number of longest ascending subsequences at the end
2. Then find the longest subsequence and mark it
3. Finally, count the number of occurrences of the longest subsequence and return

Code

/** * @param {number[]} nums * @return {number} */
var findNumberOfLIS = function(nums) {
    
    //  initialization dp Array 
    let len = nums.length;
    let dp = Array(len).fill(1);
    let count = Array(len).fill(1);
    let res = 0;
    //  Find the longest subsequence and mark it 
    for(let i = 0; i < len; i++) {
    
        for(let j = 0; j < i; j++) {
    
            if(nums[i] > nums[j]) {
    
                // Math.max... Writing 
                if(dp[j]+1 > dp[i]) {
    
                    dp[i] = dp[j]+1
                    count[i] = count[j] //  The number of longest increasing subsequences 
                    //  In fact, it is to consider the equal situation 
                }else if(dp[j]+1 === dp[i]) {
    
                    count[i] += count[j]
                }
            }
        }
    }
    //  Statistics  max  Number of occurrences 
    let max = Math.max(...dp);
    //  Here I want to count all LIS The number of must be traversed 
    for (let i = 0; i < len; i ++) if(dp[i] === max) res += count[i];
    return res;
};