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!