Longest Increasing Subsequence
'N' students are standing in a row. You are given the height of every student standing in the row. Your task is to find the longest strictly increasing subsequence of heights from the row such that the relative order of the students does not change.

A subsequence is a sequence that can be derived from another sequence by deleting zero or more elements without changing the order of the remaining elements.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. The first line of each test case contains an integer ‘N’ , the number of students in the row. The second line of each test case contains ‘N’ space separated integers representing the height of every student in the row.

Output format:

For each test case, return the length of longest strictly increasing subsequence of heights.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1

Question

Longest Increasing Subsequence

'N' students are standing in a row. You are given the height of every student standing in the row. Your task is to find the longest strictly increasing subsequence of heights from the row such that the relative order of the students does not change.

A subsequence is a sequence that can be derived from another sequence by deleting zero or more elements without changing the order of the remaining elements.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains an integer ‘N’ , the number of students in the row. 

The second line of each test case contains ‘N’ space separated integers representing the height of every student in the row.

Output format:

For each test case, return the length of longest strictly increasing subsequence of heights.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 200
1 <= heights[i] <=10^9

Time Limit: 1 sec

Accepted Answer

This is a variation of the standard LIS and LCS problem.

Accepted Answer

Brute force approach

The idea is to find strictly increasing subsequences for all the elements of the array once including the elements in the sequence and once excluding it. In order to do this, we use a recursive function, 'LIS_HELPER' which returns the length of LIS possible from the current element (maximum of the lengths of subsequences once including the current element and once excluding it).

Algorithm:

Recursive Function: 'LIS_HELPER'(heights, 'PRE', 'CURR'), where ‘heights’ is the list of heights, ‘'PRE'’ is the previous height considered in the current subsequence and 'CURR’ is the index of the current element of the height array.
Base condition => if 'CURR' = ‘N’ , return 0
There will be two cases :
If the current height is larger than the previous height included in the LIS : In this case we once include the current height in the LIS and once exclude the current height from the LIS and return the maximum of lengths obtained from both the cases.
If the current height is smaller or equal to the previous height included in the LIS : we cannot include the current height in the LIS and thus return the length of the LIS that we obtain by excluding the current height.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of students in the row.

We are using recursion. So O(N) space will be taken by the recursion stack. Thus the final space complexity is O(N).

Time Complexity: O(2^n)Explanation:

O(2^N) where ‘N’ is the number of students in the row.

Every student has two options in the worst case, whether to be a part of the current subsequence or not. This leads to a time complexity of O(2*2*2……...N terms). Thus, the total time complexity is O(2^N).

C++ (g++ 5.4)

/*
	Time complexity: O(2^N) 
	Space complexity: O(N)
	
	where 'N' is the total number of students in the row.
*/

int LISHelper(vector heights, int n, int prev, int curr){
	// All the heights has been processed.
	if(curr == n){
		return 0;
	}
	// Length of LIS including the current height.
	int include = 0;
	
	// If previous height of the LIS is less than current height.
	if(prev < heights[curr]){
		include = 1 + LISHelper(heights, n, heights[curr], curr + 1);
	}
	// Length of LIS excluding the current height.
	int exclude = 0;
	exclude = LISHelper(heights, n, prev, curr + 1);
	
	// Return the length of longest of two LIS formed.
	return max(include, exclude);
}

int LIS(vector &heights, int n){
	
	return LISHelper(heights, n, 0, 0);
		
}

Java (SE 1.8)

/*
    Time complexity: O(2^N) 
    Space complexity: O(N)
  
    where 'N' is the total number of students in the row.
*/
	
import java.util.ArrayList;

public class Solution {

  public static int LISHelper(ArrayList < Integer > heights, int n, int prev, int curr) {
    // All the heights has been processed.
    if (curr == n) {
      return 0;
    }

    // Length of LIS including the current height.
    int include = 0;

    // If previous height of the LIS is less than current height.
    if (prev < heights.get(curr)) {
      include = 1 + LISHelper(heights, n, heights.get(curr), curr + 1);
    }

    // Length of LIS excluding the current height.
    int exclude = 0;
    exclude = LISHelper(heights, n, prev, curr + 1);

    // Return the length of longest of two LIS formed.
    return Math.max(include, exclude);
  }

  public static int LIS(ArrayList < Integer > heights, int n) {
    return LISHelper(heights, n, 0, 0);
  }
}

Python (3.5)

'''

	Time complexity: O(2^N) 

	Space complexity: O(N)

	

	where N is the total number of students in the row.

'''





def LISHelper(heights, n, prev, curr):



    # All the heights has been processed.

    if(curr == n):

        return 0



    # Length of LIS including the current height.

    include = 0



    # If previous height of the LIS is less than current height.

    if(prev < heights[curr]):

        include = 1 + LISHelper(heights, n, heights[curr], curr + 1)



    # Length of LIS excluding the current height.

    exclude = 0

    exclude = LISHelper(heights, n, prev, curr + 1)



    # Return the length of longest of two LIS formed.

    return max(include, exclude)





def LIS(heights, n):

    return LISHelper(heights, n, 0, 0)

Accepted Answer

Memoization approach

LIS => Longest Increasing Subsequence.

Here, LIS(4) corresponds to LIS found up to index 4. LIS(4) will be calculated with the help of LIS(3), LIS(2), LIS(1).

Now, LIS(3) is calculated using the values of LIS(2) and LIS(1).

As you can see in the figure above this leads to recomputation of the same data again and again.

The idea is the same as the previous approach, but in the previous approach, many recursive calls were made again and again with the same parameters. This can be eliminated by storing the value obtained from a particular call in a 2d array, called the 'MEMO' array. 'MEMO'[i][j] stores the length of the LIS possible using 'HEIGHTS'[i] as the previous height(included / not included in LIS), and 'HEIGHTS'[j] as the current height(included / not included in LIS).

Algorithm:

An array, 'MEMO', of size ‘N*N’ is taken.
Recursive Function: 'LIS_HELPER'( 'HEIGHTS', 'PREV', 'CURR'), where ‘HEIGHT’ is the list of 'HEIGHTS', ‘'PREV'’ is the previous index considered in the current subsequence and 'CURR' is the index of the current element of the height array. The initial call of this function will have 'PREV' = -1 and 'CURR' = 0 as arguments.
Base condition => 'CURR' = ‘N’ , return 0
If the value at 'MEMO'['PREV'+1]['CURR'] is not -1, use this value, that is, return it.
There will be two cases :
If the current height is larger than the previous height included in the LIS: In this case, we once include the current height in the LIS and once exclude the current height from the LIS and return the maximum of lengths obtained from both the cases.
If the current height is smaller or equal to the previous height included in the LIS: we exclude it from the LIS and return the length of the LIS obtained.
Update the value returned by above recursive call in 'MEMO'['PREV'+1]['CURR']

Space Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ is the number of students in the row.

We are using recursion which takes O(N) space in the worst case for the recursion stack. The memo array of size N*N is used. Thus, the final space complexity is O(N) + O(N^2) = O(N^2).

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ is the number of students in the row.

For every element of the heights array, we are finding the length of all the increasing subsequences ending at it. The size of the recursion tree can go up to N^2. Thus, the total time complexity is O(N^2).

Java (SE 1.8)

/*
    Time complexity: O(N^2) 
    Space complexity: O(N^2)
  
    where 'N' is the total number of students in the row.
*/

import java.util.ArrayList;

public class Solution {
  public static int LISHelper(ArrayList < Integer > heights, int n, int prev, int curr, int[][] memo) {

    // All the heights has been processed.
    if (curr == n) {
      return 0;
    }

    if (memo[prev + 1][curr] >= 0) {
      return memo[prev + 1][curr];
    }
    
    // Length of LIS including the current height.
    int include = 0;

    // If the LIS is empty or if the previous height of the LIS is less than current height.
    if (prev < 0 || heights.get(prev) < heights.get(curr)) {
      include = 1 + LISHelper(heights, n, curr, curr + 1, memo);
    }

    // Length of LIS excluding the current height.
    int exclude = LISHelper(heights, n, prev, curr + 1, memo);

    // Return the length of longest of two LIS formed.
    memo[prev + 1][curr] = Math.max(include, exclude);
    return memo[prev + 1][curr];
  }

  public static int LIS(ArrayList < Integer > heights, int n) {
    int[][] memo = new int[n][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        memo[i][j] = -1;
      }
    }

    return LISHelper(heights, n, -1, 0, memo);
  }
}

Python (3.5)

'''

	Time complexity: O(N^2)

	Space complexity: O(N^2)



	where N is the total number of students in the row.

'''





def LISHelper(heights, n, prev, curr, memo):



    # All the heights has been processed.

    if(curr == n):

        return 0



    if(memo[prev + 1][curr] >= 0):

        return memo[prev + 1][curr]



    # Length of LIS including the current height.

    include = 0



    # If the LIS is empty or if the previous height of the LIS is less than current height.

    if(prev < 0 or heights[prev] < heights[curr]):

        include = 1 + LISHelper(heights, n, curr, curr + 1, memo)



    # Length of LIS excluding the current height.

    exclude = LISHelper(heights, n, prev, curr + 1, memo)



    # Return the length of longest of two LIS formed.

    memo[prev + 1][curr] = max(include, exclude)

    return memo[prev + 1][curr]





def LIS(heights, n):

    memo = [[-1 for i in range(n)] for j in range(n)]



    return LISHelper(heights, n, -1, 0, memo)

C++ (g++ 5.4)

/*

	Time complexity: O(N^2) 

	Space complexity: O(N^2)

	

	where 'N' is the total number of students in the row.

*/



int LISHelper(vector heights, int n, int prev, int curr, vector> &memo)

{



	// All the heights has been processed.

	if (curr == n)

	{

		return 0;

	}



	if (memo[prev + 1][curr] >= 0)

	{

		return memo[prev + 1][curr];

	}

	

	// Length of LIS including the current height.

	int include = 0;



	// If the LIS is empty or if the previous height of the LIS is less than current height.

	if (prev < 0 || heights[prev] < heights[curr])

	{

		include = 1 + LISHelper(heights, n, curr, curr + 1, memo);

	}



	// Length of LIS excluding the current height.

	int exclude = LISHelper(heights, n, prev, curr + 1, memo);



	// Return the length of longest of two LIS formed.

	memo[prev + 1][curr] = max(include, exclude);

	return memo[prev + 1][curr];

}



int LIS(vector &heights, int n)

{



	vector> memo(n, vector(n, -1));



	return LISHelper(heights, n, -1, 0, memo);

}

Accepted Answer

Dynamic Programming

This approach relies on the fact that the LIS possible upto ith index is independent of the elements coming after the ith index. Thus, for every index we will store the length of LIS possible upto that index in an array, say 'DP' array. For every index there will be two cases :

Iterate over the indices for all ‘j’ such that 0 <= j <= i-1, and if the value at 'HEIGHTS'[j] is less than the value at 'HEIGHTS'[i], include the current element in the LIS and check whether its length is greater than the longest length found so far.
Find the length of LIS formed before the current index.
Return the maximum of the two cases.

Algorithm:

Take a 'DP' array of size ‘N’ and initialize all its values with 0.
'DP'[0] = 1
For every index ‘i’ of the 'HEIGHTS' array
Iterate over the indices for all ‘j’ such that 0 <= j <= i-1, and if the value at 'HEIGHTS'[j] is less than the value at 'HEIGHTS'[i], 'DP'[i] = max('DP'[i], 1+'DP'[j]).
At the end of the above iteration, 'DP'[i] = max('DP'[i], 'MAX_VALUE'). 'MAX_VALUE' is the length of LIS found before the current index.
Update the value of 'MAX_VALUE' = max('MAX_VALUE', 'DP'[i]).
Return the value of 'DP'[N-1] that is the length of LIS found upto the last value of the input.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of students in the row.

We are using a dp array which stores the LIS found upto the current index. Thus, the final space complexity is O(N).

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ is the number of students in the row.

For every element of the heights array, we are finding the length of all the increasing subsequences that have been found before it. Thus, the total time complexity is O(N^2).

Java (SE 1.8)

/*
	Time complexity: O(N^2) 
	Space complexity: O(N)
	
	where 'N' is the total number of students in the row.
*/

import java.util.ArrayList;

public class Solution {

  public static int LIS(ArrayList < Integer > heights, int n) {
    // To store length of LIS.
    int[] dp = new int[n];

    // LIS with one element.
    dp[0] = 1;

    // Length of LIS upto now.
    int maxValue = 1;

    // For all the elements of heights array, find the length of LIS that can be formed up to that element.
    for (int i = 1; i < n; i++) {
      int temp = 0;
      for (int j = 0; j < i; j++) {
        // If current height 'heights[i]' can be a appended to the LIS ending at heights[j].
        if (heights.get(j) < heights.get(i)) {
          temp = Math.max(temp, dp[j]);
        }
      }

      // Update the value of dp[i] with the length of LIS that can be formed up to heights[i].
      dp[i] = temp + 1;

      // Update maxValue.
      maxValue = Math.max(dp[i], maxValue);
    }

    return maxValue;
  }
}

Python (3.5)

'''

	Time complexity: O(N^2)

	Space complexity: O(N)



	where N is the total number of students in the row.

'''





def LIS(heights, n):



    # To store length of LIS.

    dp = [0] * n



    # LIS with one element.

    dp[0] = 1



    # Length of LIS up to now.

    maxValue = 1



    # For all the elements of heights array, find the length of LIS that can be formed up to that element.

    for i in range(1, n):



        temp = 0

        for j in range(i):



            # If current height 'heights[i]' can be a appended to the LIS ending at heights[j].

            if(heights[j] < heights[i]):

                temp = max(temp, dp[j])



        # Update the value of dp[i] with the length of LIS that can be formed up to heights[i].

        dp[i] = temp + 1



        # Update maxValue.

        maxValue = max(dp[i], maxValue)



    return maxValue

C++ (g++ 5.4)

/*
	Time complexity: O(N^2) 
	Space complexity: O(N)
	
	where 'N' is the total number of students in the row.
*/

int LIS(vector &heights, int n){
	
	// To store length of LIS.
	int dp[n];
	
	// LIS with one element.
	dp[0] = 1;
	
	// Length of LIS upto now.
	int maxValue = 1;
	
	// For all the elements of heights array, find the length of LIS that can be formed up to that element.
	for(int i = 1; i < n; i++){
		int temp = 0;
		for(int j = 0; j < i; j++){
			// If current height 'heights[i]' can be a appended to the LIS ending at heights[j].
			if(heights[j] < heights[i]){
				temp = max(temp, dp[j]);
			}
		}
		
		// Update the value of dp[i] with the length of LIS that can be formed up to heights[i].
		dp[i] = temp + 1;
		
		// Update maxValue.
		maxValue = max(dp[i], maxValue);
	}
	
	return maxValue;
}

'N' students are standing in a row. You are given the height of every student standing in the row. Your task is to find the longest strictly increasing subsequence of heights from the row such that the relative order of the students does not change.

Input format:

Output format:

Note:

Constraints :

Top SAP Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in SAP Software Developer