Home » Technical Interview Questions » Dynamic Programming Interview Questions » Number Of Longest Increasing Subsequence

Number Of Longest Increasing Subsequence


Reading Time - 4 mins


Difficulty Level Easy

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.
READ  Collect maximum points in a grid using two traversals

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.

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions