Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags


The longest increasing subsequence problem

Educative Answers Team

The longest increasing subsequence problem looks for numbers, in ascending order, that build the increasing subsequence in an array. To extract the subsequence, the array that stores the integer data is traversed. There will be more than one increasing subsequence, but the sequence with the maximum increasing elements is the one that is displayed as an output.

The algorithm

The idea is to use recursion to solve this problem.

  1. Find as many subsequences as possible for the current number.

  2. If the current item is greater than the previous element in the subsequence, include the current item in the subsequence and recur for the remaining items.

  3. Exclude the current item from the sequence and recur for the remaining items.

  4. Finally, we return the maximum value that we’ve gotten by including or excluding the current item. ​

The base case of ​recursion happens when no items are left.

1 of 19


The following code takes an array and returns the length of the longest increasing subsequence found:

#include <iostream>
#include <climits>
using namespace std;

// Function to find length of longest increasing subsequence
int LIS(int arr[], int i, int n, int prev)
	// Base case: if nothing is remaining
	if (i == n)
		return 0;

	// case 1: exclude the current element and process the
	// remaining elements
	int exclude = LIS(arr, i + 1, n, prev);

	// case 2: include the current element if it is greater
	// than previous element in LIS
	int include = 0;
	if (arr[i] > prev)
		include = 1 + LIS(arr, i + 1, n, arr[i]);

	// return maximum of above two choices
	return max(include, exclude);

// main function
int main()
	int arr[] = { 3, 2, 6, 4, 5, 1 };
	int n = sizeof(arr) / sizeof(arr[0]);

	cout << "Length of the longest increasing subsequence is " 
	<< LIS(arr, 0, n, INT_MIN);

	return 0;


Copyright ©2022 Educative, Inc. All rights reserved

View all Courses

Keep Exploring