Solution:
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
int n=nums.size();
int *length=new int[n];
int *count=new int[n];
for(int i=0;i<n;i++)
{
length[i]=1;
count[i]=1;
}
for(int i=1;i<n;i++)
{
for(int j=0;j<=i-1;j++)
{
if(nums[j]<nums[i])
{
if(length[j]+1>length[i])
{
length[i]=length[j]+1;
count[i]=count[j];
}
else if(length[j]+1==length[i])
{
count[i]+=count[j];
}
}
}
}
int t=*max_element(length,length+n);
int result=0;
for(int i=0;i<n;i++)
{ if(length[i]==t)
result+=count[i];
}
return result ;
}
};
- Here we had to count the LIS. So we maintained another array named count.
- The idea is to use two arrays len[n] and cnt[n] to record the maximum length of Increasing Subsequence and the
- coresponding number of these sequence which ends with nums[i], respectively. That is:
*
- len[i]: the length of the Longest Increasing Subsequence which ends with nums[i].
*
- cnt[i]: the number of the Longest Increasing Subsequence which ends with nums[i].
*
- Then, the result is the sum of each cnt[i] while its corresponding len[i] is the maximum length.
*
- For example, we have nums = [1,3,5,4,7]. Then after we have processed till 4, our len and count array will be like
- len = [1,2,3,3,4]
- count = [1,1,1,1,2].
- We see that when we have two increasing subseq of len 3, and need one more element to increase both lengths to 4, then we have a
- number of count1 + count2 ways to find a lIS of length 4. Thats why we add both count[i] and count[j] when len[i] == len[j]+1
- Thats because when we have len[i] already equal to len[j]+1 means that there already exists a subseq which can make an LIS of len[j]+1
- so we need to count its number of ways too!
Top comments (0)