673. Number of Longest Increasing Subsequence

Problem Statement

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

• -106 <= nums[i] <= 106

Intuition

Maintain a count array to keep count along with the dp array

Logic is, when you get the same 1 + dp[prev] == dp[index]
Means you got the sequence count again 
So you incr the count of the count array

Links

https://leetcode.com/problems/number-of-longest-increasing-subsequence/description/

Video Links

https://www.youtube.com/watch?v=cKVl1TFdNXg&t=1004s&ab_channel=takeUforward

Approach 1:

Maintain dp & count array

C++

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

        for(int index=1; index<n; index++){
            for(int prev=0; prev<index; prev++){

                if(nums[prev] < nums[index] and 1+dp[prev] > dp[index]){
                    dp[index] = 1+dp[prev];
                    ct[index] = ct[prev];
                }

                else if(nums[prev] < nums[index] and 1+dp[prev] == dp[index])
                    ct[index] += ct[prev];
            }

            maxi = max( maxi, dp[index]);
        }

        int nos = 0;
        // sum of all the count having seq as maxi
        // LIS can be at different position

        for(int i=0; i<n; i++){
            if(dp[i]==maxi)
                nos += ct[i];
        }

        return nos;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems