Number of Longest Increasing Subsequence.cpp

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int len = nums.size(), maxLen = 0, maxNum = 0;
        
        //dp[0][i] lenght of LIS ending at i
        //dp[1][i] numbers of LISs ending at i
        vector<vector<int>> dp(2, vector<int>(len, 0));
        
        for(int i = 0; i < len; ++i)
        {
            int currLen = 1, currNum = 1;
            for(int j = 0; j < i; ++j)
            {
                if(nums[j] < nums[i])
                {
                    if(dp[0][j] + 1 > currLen)
                    {
                        currLen = dp[0][j] + 1;
                        currNum = dp[1][j];
                    }
                    else if(dp[0][j] + 1 == currLen)
                        currNum += dp[1][j];
                }
            }
            dp[0][i] = currLen;
            dp[1][i] = currNum;
            if(currLen > maxLen)
            {
                maxLen = currLen;
                maxNum = currNum;
            }
            else if(currLen == maxLen)
                maxNum += currNum;
        }
        return maxNum;
    }
};