673. Number of Longest Increasing Subsequence

#code


class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        int maxlen = 1;
        vector<int> lis(n,1),cnt(n,1);
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i] > nums[j]){
                    if(lis[j]+1 > lis[i]){
                        lis[i] = lis[j]+1;
                        cnt[i] = cnt[j];
                    }
                    else if(lis[j]+1 == lis[i])
                        cnt[i] += cnt[j];
                } 
            }
            maxlen = max(maxlen,lis[i]);
        }
        int res = 0;
        
        for(int i=0;i<n;i++){
            if(lis[i] == maxlen)
                res += cnt[i];
        }
        return res;
    }
};