Number Of Longest Increasing Subsequence - Leetcode Solution

Number Of Longest Increasing Subsequence problem on Leetcode asks you to find the number of longest increasing subsequence in an array of integers. The solution to this problem can be achieved using dynamic programming approach.

In order to solve this problem, first, we can create a dp array of the same length as the given array and initialize it with 1, because every element in the array is a subsequence of length 1.

Then, we can implement two nested loops, the outer loop will iterate through the array and the inner loop will iterate through elements before the current element. We will check if the element that we are currently iterating is greater than the previous element, if so we can increase the length of the subsequence by 1 and store it in the dp array.

We can also keep another dp2 array to keep track of the number of subsequences that can be formed up to this point. We can initialize it with 1 as well, because each element in the array forms one subsequence of length 1.

We can again use nested loops here, the outer loop will iterate through the array and the inner loop will iterate through elements before the current element. We will check if the element that we are currently iterating is greater than the previous element, if so we can check whether dp[i] is less than or equal to dp[j] + 1, and if it is, we can add the value of dp2[j] to dp2[i].

Finally, we can loop through the dp array and find the maximum value, which will give us the length of the longest increasing subsequence. We can then loop through dp2 array again and add the values of dp2[i] where dp[i] is equal to the length of the longest increasing subsequence.

Here is the code implementation of the solution:

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n,1);
        vector<int> dp2(n,1);
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    if(dp[i]<=dp[j]+1){
                        dp[i] = dp[j]+1;
                        dp2[i] = dp2[j];
                    }
                    else if(dp[i] == dp[j]+1){
                        dp2[i] += dp2[j];
                    }
                }
            }
        }
        int maxx = *max_element(dp.begin(),dp.end());
        int res = 0;
        for(int i=0;i<n;i++){
            if(dp[i] == maxx){
                res += dp2[i];
            }
        }
        return res;
    }
};

1