Leetcode•Apr 10, 2026

Number of Longest Increasing Subsequence

Hazrat Ali

Leetcode

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

Notice that the sequence has to be strictly increasing.

 

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 the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.

Solution
var findNumberOfLIS = function(nums) {
    const n = nums.length;
   
    const len = new Array(n).fill(1);
    const cnt = new Array(n).fill(1);

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (len[j] + 1 > len[i]) {
                    len[i] = len[j] + 1;
                    cnt[i] = cnt[j];
                }
                else if (len[j] + 1 === len[i]) {
                    cnt[i] += cnt[j];
                }
            }
        }
    }

    let maxLen = Math.max(...len);
    let result = 0;

    for (let i = 0; i < n; i++) {
        if (len[i] === maxLen) {
            result += cnt[i];
        }
    }

    return result;
};



Comments