Number of Longest Increasing Subsequence

The simplest approach is to generate all possible subsequences present in the given array ‘arr’ and count the increasing subsequences of maximum length. Print the count after checking all subsequences.

For every element in the array, there are two choices, either to include it in the subsequence or not include it. Apply this for every element in the array starting from index 0 until we reach the last index. After we reach the last index, we check if this is an increasing subsequence and if so, then we increment the count of the size of this subsequence by 1.

At last, we simply traverse the count array and find the frequency of the max count.

The steps are as follows :

1. Create a recursive function and pass three arguments :
   • array ‘arr’
   • index ‘i’
   • subarray ‘subArr’ (This will store the current subsequence)
2. When we reach the end of array ‘arr’ i.e. ‘i’ is equal to ‘n’, we check if this is an increasing subsequence so we increment its count by one.
3. Create an array ‘count’, where at each index ‘i’ we store the number of LIS of length ‘i’.
4. If we have not reached the end of ‘arr’, then we make two recursive calls, one without including the current element and the other including the current element.
5. At last, traverse the ‘count’ array and find the frequency of max count.

In the above approach, we were generating all possible subsequences. It will definitely result in TLE. We can think of a solution where we can use something we already calculated. We can maintain a ‘length’ array where ‘length’[i] denotes the length of LIS ending at ‘arr’[i]. We also maintain an array ‘count’ wherein each entry ‘count’[i] we store the number of LISs whose size equals 'length’[i].

'length’[i] can be recursively calculated as: 

    ‘length’[i] = 1 + max( ‘length’[j] ) where 0 < j < i and ‘arr’[j] < ‘arr’[i]; or

    'length’[i] = 1, if no such j exists.

But if we calculate this directly with the help of recursion, it will also lead to TLE because the time complexity is exponential ~O(N ^ N). 

Can we do better?

We can see that there are many subproblems in the above recursive solution which are solved again and again. So this problem has Overlapping Substructure property and recomputation of same subproblems can be avoided by either using Memoization or Tabulation.

We can avoid recomputation of subproblems by using tabulation as shown below

Let's take an example ‘arr’ = [1,4,2,5,3].

Initially, all elements in 'length’ and ‘count’ are 1.

We start from ‘i’ equal to 1 i.e. ‘num’ is 4.

We see that 4 is greater than 1 and 'length’[0] + 1 is greater than 'length’[1], so we update 'length’[1] to 'length’[0] + 1 and ‘count’[1] to ‘count’[0].

Then we go to ‘i’ equal to 2 i.e. ‘num’ is 2.

We see that 2 is greater than 1 and 'length’[0] + 1 is greater than 'length’[2], so we update 'length’[2] to 'length’[0] + 1 and ‘count’[2] to ‘count’[0].

Then we go to ‘i’ equal to 3 i.e. ‘num’ is 5.

We see that 5 is greater than 1 and 'length’[0] + 1 is greater than 'length’[3], so we update 'length’[3] to 'length’[0] + 1 and ‘count’[3] to ‘count’[0].

Again we see that 5 is greater than 4 and 'length’[1] + 1 is greater than 'length’[3], so we update 'length’[3] to 'length’[1] + 1 and ‘count’ to ‘count’[1].

Again we see that 5 is greater than 2 and 'length’[2] + 1 is equal to 'length’[3], so we update ‘count’[3] to ‘count’[3] + ‘count’[2].

Now we go to ‘i’ equal to 4 i.e. ‘num’ is 3.

We see that 3 is greater than 1 and 'length’[0] + 1 is greater than 'length’[4], so we update 'length’[4] to 'length’[0] + 1 and ‘count’[4] to ‘count’[0].

Again we see that 3 is greater than 2 and 'length’[2] + 1 is greater than 'length’[4], so we update 'length’[4] to 'length’[2] + 1 and ‘count’[4] to ‘count’[2].

Now the ‘length’ array becomes [1, 2, 2, 3, 3]. So ‘maxLength’ is 3.

The ‘count’ array is [1, 1, 1, 2, 1]. 

Now we traverse the 'length’ array and observe that 'length’[3] and 'length’[4] are the same as ‘maxLength’ so we incremented ‘cnt’ by ‘count’[3] and ‘count’[4] respectively.

Hence the ‘cnt’ becomes 3 which is our answer, and the three LIS are [1, 4, 5], [1, 2, 5], [1, 2, 3].

The steps are as follows :

1. Initialize all elements in arrays 'length’ and ‘count’ to one for storing the length of the longest increasing subsequences and the count of the longest increasing subsequence at each index respectively.
2. for ‘i’ in [1 . . . N – 1]:
   • for ‘j’ in [0 . . . i – 1]:
     • If 'arr'[i] > 'arr'[j] then check for the following cases: 
       • If ('length’[j] + 1) greater than 'length’[i], then update 'length’[i] as 'length’[j] + 1 and ‘count’[i] as ‘count’[j] 
       • Else if ('length’[j] + 1) is the same as 'length’[i], then update ‘count’[i] as ‘count’[i] + ‘count’[j].
3. Find the maximum element in the array 'length’ and store it in a variable ‘maxLength’ that will give the length of LIS.
4. Initialize a variable ‘cnt’ with 0 to store the number of the longest increasing subsequence.
5. Traverse the array 'length’ and if at any index ‘idx’, 'length’[idx] is the same as ‘maxLength’ then increment the ‘cnt’ by ‘count’[idx].
6. After the above steps, print the value of ‘cnt’.

Now we have already discussed the O( n ^ 2 ) solution. There is one more optimal solution to this problem. We can solve this problem in O( n * log(n) ) time using binary search.

The idea is simple; we keep track of the longest increasing sequence (LIS) as well as the number of LIS sequences ending with the current element.

Check the code for a better understanding.

For example, let 'arr' =  [1, 3, 5, 4, 7]

I assume it is easy to see LIS for the first 3 elements is [1, 3, 5].

When we see 4, we can update LIS to have [1,3,4], but we should not discard the sequence [1, 3, 5] since it may contribute to later LIS sequences. This LIS has a length of 3 (maximum index is 2), so we keep a vector:

'table'[2] = {[5,1], [4,1]}, indicating at LIS index 2, we could have 1 sequence ending with 5 and another sequence ending with 4.

Then we see 7. We see 7 has to be added to the end of the previous LIS, but it could be added to the LIS ending with 5 or 4. So we will have 'table'[3] = {[7, 2]}.

In general, for any current element, we will need to find out the index just before its insert point in LIS. In the previous example, for number 7 to be inserted at index 3, we need to check 'table'[2] to update the number of possible paths for the current number. In my program, this is what ‘k’ is.

Also, for each LIS insertion at index ‘i’, we are inserting it in descending order, so it would be easy to find out the exact place in 'table'[i] using binary search. In my program, I used negative numbers for easy binary search.

Another trick is I am only keeping the prefix sum of all paths for 'table'[i]. In this way, the number of paths ‘k’ can be obtained in O(1).
 

The steps are as follows :

1. Create a 2d array ‘table’ where ‘table’[i] stores all possible elements at which LIS of length ‘i’ + 1 ends. Also, we need a ‘paths’ array where we can store at index ‘i’, an array whose last element will represent the number of LIS of length ‘i’ + 1. We will perform prefix queries on this array.
2. We also create a ‘lis’ array where at index ‘i’ we store the last element at which LIS of length ‘i’ + 1 ends. This will be an increasing sequence, so will directly binary search to find out the correct insert position of the current element.
3. for ‘a’ in [0 . . ‘n’ - 1]:
   • ‘i’ = lower_bound('lis', ‘arr’[a]), correct insert position of ‘arr’[a] in ‘lis’.
   • Initialize ‘k’ to 1.
   • if i > 0:
     • ‘j’ = upper_bound('table'[i], - 'arr'[a])
     • ‘k’ = ‘paths’[i - 1].back() - ‘paths’[i - 1][j]
   • 'table'[i].push_back(-'arr'[a]) 
   • If ‘i’ is equal to max size of increasing sequence i.e. ‘i’ == ‘lis’.size():
     • 'lis'.push_back(arr[a])
     • ‘paths’.push_back({0, k}), we push zero because we can directly subtract for prefix sum else we need to add one edge case.
   • else:
     • ‘lis’[i] = ‘arr’[a]
     • ‘paths’.push_back('paths'[i].back() + k)