Number of Longest Increasing Subsequence

Problem

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

Constraints:

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

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var findNumberOfLIS = function(nums) {
    let max = 1; // overall max length of subsequence
    let count = 1; // overall count of max length subsequence
    const dp = [{ max, count }];

    for (let i = 1; i < nums.length; i++) {
        dp.push({ max: 1, count: 1 });
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) { // can end at nums[i]
                if (dp[i].max < dp[j].max + 1) { // new local max
                    dp[i].max = dp[j].max + 1;
                    dp[i].count = dp[j].count;
                } else if (dp[i].max === dp[j].max + 1) { // same local max
                    dp[i].count += dp[j].count;
                }
            }
        }
        if (dp[i].max > max) { // new global max => new global count
            max = dp[i].max;
            count = dp[i].count;
        } else if (dp[i].max === max) { // same global max => increment global count
            count += dp[i].count;
        }
    }
    return count;
};

We will implement a DP solution. Let dp[i] have two properties, max and count. Let dp[i].max be the length of the longest increasing subsequence ending at and including nums[i]. Let dp[i].count be the number of increasing subsequences of length dp[i].max ending at and including nums[i].

For the base case, if i = 0, then dp[0].max = 1 and dp[0].count = 1 since there's only 1 possible subsequence which is nums[0] itself.
For the recursive case, dp[i].max is computed the same way as the Longest Increasing Subsequence problem. For dp[i].count:
- When we encounter a new subsequence with length greater than dp[i].max, we update dp[i].count to the count of the previous value in this new subsequence (ie. dp[i].count will be reset to dp[j].count since the old count is no longer relevant for the new max length subsequence).
- When we encounter a new subsequence with length same as dp[i].max, we increment dp[i].count by the count of the previous value in this new subsequence (ie. dp[i].count will be incremented by dp[j].count since the old count is still relevant).

Note that we also keep an overall max and count variable and update the two as needed after every i (in a similar manner as the recursive case for dp).

Problem​

Solution​

Problem

Solution