Untitled
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