Number of Longest Increasing Subsequence

Link

Description

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.

Constraints:

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

Solution

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1), count(n, 1);

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j];
                    }
                }
            }
        }

        int maxVal = *max_element(dp.begin(), dp.end());
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == maxVal) res += count[i];
        }
        return res;
    }
};

• Time complexity: \(O(n^2)\);
• Space complexity: \(O(n)\).

Variables:

1. dp[i]: The length of the longest increasing subsequence ending at index i.
2. count[i]: The number of longest increasing subsequences ending at index i.

Logic:

• We iterate over each element nums[i] in the array.
• For each nums[i], we check all previous elements nums[j] (j < i).
• If nums[i] is greater than nums[j], it means nums[i] can extend the increasing subsequence ending at nums[j].
• We then update dp[i] and count[i] based on the conditions:
  • If the length of the increasing subsequence ending at nums[j] plus 1 (dp[j] + 1) is greater than the current dp[i], we found a longer subsequence ending at i, so we update dp[i] and set count[i] to count[j].
  • If dp[j] + 1 is equal to dp[i], it means we found another subsequence of the same length as the longest found so far, so we add count[j] to count[i].
• Finally, we find the length of the longest increasing subsequence (maxVal) and sum up all count[i] where dp[i] is equal to maxVal.

State Transformation Equations:

1. dp[i] = max(dp[i], dp[j] + 1) for all j < i and nums[i] > nums[j].
2. count[i] is updated as follows:
3. count[i] = count[j] if dp[j] + 1 > dp[i].
4. count[i] += count[j] if dp[j] + 1 == dp[i].