Number of Longest Increasing Subsequence in C++

Suppose we have one unsorted array of integers. we have to find the number of longest increasing subsequence, so if the input is like [1, 3, 5, 4, 7], then the output will be 2, as increasing subsequence are [1,3,5,7] and [1, 3, 4, 7]

To solve this, we will follow these steps −

• n := size of the num array, create two arrays len and cnt of size n, and fill them with value 1.
• lis := 1
• for i in range 1 to n
  • for j in range 0 to i – 1
    • if nums[i] > nums[j], then
      • if len[j] + 1 > len[i], then len[i] := len[j] + 1, and cnt[i] := cnt[j]
      • otherwise when len[j] + 1 = len[j], then cnt[i] := cnt[i] + cnt[j]
    • lis := max of lis and len[j]
• ans := 0
• for i in range 0 to n – 1
  • if len[i] = lis, then ans := ans + cnt[j]
• return ans

Example(C++)

Let us see the following implementation to get better understanding −

 Live Demo

#include <bits/stdc++.h> using namespace std; class Solution { public:    int findNumberOfLIS(vector<int>& nums) {       int n = nums.size();       vector <int> len(n, 1), cnt(n, 1);       int lis = 1;       for(int i = 1; i < n; i++){          for(int j = 0; j < i; j++){             if(nums[i] > nums[j]){                if(len[j] + 1 > len[i]){                   len[i] = len[j] + 1;                   cnt[i] = cnt[j];                }                else if(len[j] + 1 == len[i]){                   cnt[i] += cnt[j];                }             }             lis = max(lis, len[i]);          }       }       int ans = 0;       for(int i = 0; i < n; i++){          if(len[i] == lis)ans += cnt[i];       }       return ans;    } }; main(){    Solution ob;    vector<int> v = {1,3,5,4,7};    cout << (ob.findNumberOfLIS(v)); }

Input

[1,3,5,4,7]

Output

2