Untitled

 avatar
unknown
plain_text
a year ago
856 B
5
Indexable
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int>dp(n,1); //length of LIS starting at index i
        vector<int>count(n,1); // no of LIS starting at index i
        int M=INT_MIN, res=1;
        for(int i=n-1;i>=0;i--){
            int maxlen=dp[i];
            int maxcnt=count[i];
            for(int j=i+1;j<n;j++){
                if(nums[j]>nums[i]){
                    if(dp[j]+1>maxlen){
                        maxlen=dp[j]+1;
                        maxcnt=count[j];
                    }else if(dp[j]+1==maxlen) maxcnt+=count[j];
                }
            }
            dp[i]=maxlen; count[i]=maxcnt;
            if(dp[i]==M) res+=count[i];
            if(dp[i]>M){
                res=count[i];
                M=dp[i];
            }
        }
        return res;
    }
};
Editor is loading...
Leave a Comment