Number Of Longest Increasing Subsequence


Difficulty Level Medium
Frequently asked in Amazon Samsung Zoho
Array Dynamic Programming

Problem Statement

The problem “Number Of Longest Increasing Subsequence” states that you are given an array a[ ] of size n. Print the number of longest increasing subsequences in it.

Number Of Longest Increasing Subsequence

Example

a[ ] = {1, 2, 5, 4, 7}
2

Explanation: The longest increasing subsequences can be seen in the above image.

Input : a[ ] = {1, 2, 3, 4, 5}

Output : 1    (1,2,3,4,5 is the longest sub-sequence here)

Algorithm for Number Of Longest Increasing Subsequence

  1. Initialize an array a[ ] of integer type of size n.
  2. Create a function to find number of the longest increasing sub-sequences which accept an array of integer type and it’s size as it’s parameters.
  3. Create two arrays of integer type len and cnt of size n and initialize every element of both the arrays as 1. Also, initialize an integer variable lis = 1.
  4. Traverse from 1 till n-1 using i and create an inner loop from 0 to i-1.
  5. Check if the element in array a[ ] at current index of outer loop is greater than the element in array a[ ] at the current index of the inner loop, check if the value + 1 in array len[ ] at current index of inner loop is greater than the element in array len[ ] at current index of outer loop, update the value in array len[ ] at current index of outer loop as the value + 1 in array len[ ] at current index of inner loop and the value in array cnt[ ] at current index of outer loop as the value in array cnt[ ] at current index of inner loop.
  6. Else if the value + 1 in array if len[ ] at current index of inner loop is equal to the element in array len[ ] at current index of outer loop, update the value in array cnt[ ] at current index of outer loop as the sum of the value in array cnt[ ] at current index of inner loop and the outer loop itself.
  7. Store the maximum of lis and len[i] in lis.
  8. Initialize a variable ans as 0.
  9. Traverse again from 0 to n-1 and check if len[i] is equal to lis add the value at the current index of cnt in ans.
  10. Return ans.

Code

C++ Program to find number of longest increasing subsequence

#include <bits/stdc++.h>
using namespace std;

class Longestsubseq{
    public:
        int numOfIncSubseq(int a[], int n){
        
        int len[n], cnt[n]; 
        
        for(int i=0; i<n; i++){
            len[i]=1;
            cnt[i]=1;
        }
        
        int lis = 1;
        for(int i=1; i<n; i++){
            for(int j=0; j<i; j++){
                if(a[i] > a[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;
    }
};

int main(){
    Longestsubseq ls;
    
    int a[] = {1,2,5,4,7};
    int n = sizeof(a)/sizeof(a[0]);
    
    cout<<(ls.numOfIncSubseq(a, n));
    
    return 0;
}
2

Java Program to find number of longest increasing subsequence

import java.util.*;

class Longestsubseq{

    static int numOfIncSubseq(int[] a, int n){
    
        int[] len = new int[n];
        int[] cnt = new int[n]; 
        
        for(int i=0; i<n; i++){
            len[i]=1;
            cnt[i]=1;
        }
        
        int lis = 1;
        for(int i=1; i<n; i++){
            for(int j=0; j<i; j++){
                if(a[i] > a[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 = Math.max(lis, len[i]);
            }
        }
        
        int ans = 0;
        
        for(int i=0; i<n; i++){
            if(len[i] == lis)ans += cnt[i];
        }
        
        return ans;
    }
    
    public static void main (String[] args){
        int[] a = {1,2,5,4,7};
        int n = a.length;
        
        System.out.println(numOfIncSubseq(a, n));
    }
}
2

Complexity Analysis

Time Complexity

O(n*n) where n is the number of elements in the given array a[ ]. The time complexity is the same as what is required to find the longest increasing subsequence.

Space Complexity

O(n) because we used extra n space. We have used a len[] array which stores the longest increasing subsequence ending at ith element.