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 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.
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
View all Courses