## DEV Community is a community of 906,671 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Carnato

Posted on

# Number of longest common subsequence

## 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!