673. Number of Longest Increasing Subsequence

[Tcdian]

673. Number of Longest Increasing Subsequence

Given an integer array nums, return the number of longest increasing subsequences.

Example 1

Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].

Example 2

Input: nums = [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.

Constraints

• 0 <= nums.length <= 2000
• -10⁶ <= nums[i] <= 10⁶

[Tcdian]

Solution

• TypeScript Solution

function findNumberOfLIS(nums: number[]): number {
    let dp: [number, number][] = Array.from(Array(nums.length), () => [1, 1]);
    let longest = 1;
    let result = 0;
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                if (dp[j][0] + 1 > dp[i][0]) {
                    dp[i] = [dp[j][0] + 1, dp[j][1]];
                } else if (dp[j][0] + 1 === dp[i][0]) {
                    dp[i][1] += dp[j][1];
                }
            }
        }
        if (dp[i][0] > longest) {
            [longest, result] = dp[i];
        } else if (dp[i][0] === longest) {
            result += dp[i][1];
        }
    }
    return result;
};