Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

longest
increasing
subsequence
problem

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

Implementation

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;
}

RELATED TAGS

longest
increasing
subsequence
problem
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring