The longest increasing subsequence problem
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.
-
Find as many subsequences as possible for the current number.
-
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.
-
Exclude the current item from the sequence and recur for the remaining items.
-
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.
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 subsequenceint LIS(int arr[], int i, int n, int prev){// Base case: if nothing is remainingif (i == n)return 0;// case 1: exclude the current element and process the// remaining elementsint exclude = LIS(arr, i + 1, n, prev);// case 2: include the current element if it is greater// than previous element in LISint include = 0;if (arr[i] > prev)include = 1 + LIS(arr, i + 1, n, arr[i]);// return maximum of above two choicesreturn max(include, exclude);}// main functionint 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
