Given an array arr[] of size N, the task is to find the length of the Longest Increasing Subsequence (LIS) i.e., the longest possible subsequence in which the elements of the subsequence are sorted in increasing order.
Examples:
Input: arr[] = {3, 10, 2, 1, 20}
Output: 3
Explanation: The longest increasing subsequence is 3, 10, 20Input: arr[] = {3, 2}
Output:1
Explanation: The longest increasing subsequences are {3} and {2}Input: arr[] = {50, 3, 10, 7, 40, 80}
Output: 4
Explanation: The longest increasing subsequence is {3, 7, 40, 80}
Longest Increasing Sequence using Recursion:
The problem can be solved based on the following idea:
Let L(i) be the length of the LIS ending at index i such that arr[i] is the last element of the LIS. Then, L(i) can be recursively written as:
- L(i) = 1 + max(L(j) ) where 0 < j < i and arr[j] < arr[i]; or
- L(i) = 1, if no such j exists.
Formally, the length of LIS ending at index i, is 1 greater than the maximum of lengths of all LIS ending at some index j such that arr[j] < arr[i] where j < i.
We can see that the above recurrence relation follows the optimal substructure property.
Below is the implementation of the recursive approach:
C++
// A Naive C++ recursive implementation// of LIS problem#include <bits/stdc++.h>using namespace std;// To make use of recursive calls, this// function must return two things:// 1) Length of LIS ending with element// arr[n-1].// We use max_ending_here for this purpose// 2) Overall maximum as the LIS may end// with an element before arr[n-1] max_ref// is used this purpose.// The value of LIS of full array of size// n is stored in *max_ref which is// our final resultint _lis(int arr[], int n, int* max_ref){ // Base case if (n == 1) return 1; // 'max_ending_here' is length of // LIS ending with arr[n-1] int res, max_ending_here = 1; // Recursively get all LIS ending with // arr[0], arr[1] ... arr[n-2]. If // arr[i-1] is smaller than arr[n-1], // and max ending with arr[n-1] needs // to be updated, then update it for (int i = 1; i < n; i++) { res = _lis(arr, i, max_ref); if (arr[i - 1] < arr[n - 1] && res + 1 > max_ending_here) max_ending_here = res + 1; } // Compare max_ending_here with the // overall max. And update the // overall max if needed if (*max_ref < max_ending_here) *max_ref = max_ending_here; // Return length of LIS ending // with arr[n-1] return max_ending_here;}// The wrapper function for _lis()int lis(int arr[], int n){ // The max variable holds the result int max = 1; // The function _lis() stores its // result in max _lis(arr, n, &max); // Returns max return max;}// Driver program to test above functionint main(){ int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call cout << "Length of lis is " << lis(arr, n); return 0;} |
C
// A Naive C recursive implementation// of LIS problem#include <stdio.h>#include <stdlib.h>// To make use of recursive calls, this// function must return two things:// 1) Length of LIS ending with element arr[n-1].// We use max_ending_here for this purpose// 2) Overall maximum as the LIS may end with// an element before arr[n-1] max_ref is// used this purpose.// The value of LIS of full array of size n// is stored in *max_ref which is our final resultint _lis(int arr[], int n, int* max_ref){ // Base case if (n == 1) return 1; // 'max_ending_here' is length of LIS // ending with arr[n-1] int res, max_ending_here = 1; // Recursively get all LIS ending with arr[0], // arr[1] ... arr[n-2]. If arr[i-1] is smaller // than arr[n-1], and max ending with arr[n-1] // needs to be updated, then update it for (int i = 1; i < n; i++) { res = _lis(arr, i, max_ref); if (arr[i - 1] < arr[n - 1] && res + 1 > max_ending_here) max_ending_here = res + 1; } // Compare max_ending_here with the overall // max. And update the overall max if needed if (*max_ref < max_ending_here) *max_ref = max_ending_here; // Return length of LIS ending with arr[n-1] return max_ending_here;}// The wrapper function for _lis()int lis(int arr[], int n){ // The max variable holds the result int max = 1; // The function _lis() stores its result in max _lis(arr, n, &max); // returns max return max;}// Driver program to test above functionint main(){ int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call printf("Length of lis is %d", lis(arr, n)); return 0;} |
Length of lis is 5
Complexity Analysis:
- Time Complexity: O(2n) The time complexity of this recursive approach is exponential as there is a case of overlapping subproblems as explained in the recursive tree diagram above.
- Auxiliary Space: O(1). No external space is used for storing values apart from the internal stack space.
Longest Increasing Subsequence using Memoization:
If noticed carefully, we can see that the above recursive solution also follows the overlapping subproblems property i.e., same substructure solved again and again in different recursion call paths. We can avoid this using the memoization approach.
We can see that each state can be uniquely identified using two parameters:
- Current index (denotes the last index of the LIS) and
- Previous index (denotes the ending index of the previous LIS behind which the arr[i] is being concatenated).
Below is the implementation of the above approach.
C++
// C++ code of memoization approach for LIS#include <bits/stdc++.h>using namespace std;// To make use of recursive calls, this// function must return two things:// 1) Length of LIS ending with element// arr[n-1].// We use max_ending_here for this purpose// Overall maximum as the LIS may end with// an element before arr[n-1] max_ref is// used this purpose.// The value of LIS of full array of size// n is stored in *max_ref which is// our final resultint f(int idx, int prev_idx, int n, int a[], vector<vector<int> >& dp){ if (idx == n) { return 0; } if (dp[idx][prev_idx + 1] != -1) { return dp[idx][prev_idx + 1]; } int notTake = 0 + f(idx + 1, prev_idx, n, a, dp); int take = INT_MIN; if (prev_idx == -1 || a[idx] > a[prev_idx]) { take = 1 + f(idx + 1, idx, n, a, dp); } return dp[idx][prev_idx + 1] = max(take, notTake);}// Function to find length of// longest increasing subsequenceint longestSubsequence(int n, int a[]){ vector<vector<int> > dp(n + 1, vector<int>(n + 1, -1)); return f(0, -1, n, a, dp);}// Driver program to test above functionint main(){ int a[] = { 3, 10, 2, 1, 20 }; int n = sizeof(a) / sizeof(a[0]); // Function call cout << "Length of lis is " << longestSubsequence(n, a); return 0;} |
Length of lis is 3
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Longest Increasing Subsequence using Dynamic Programming:
Because of the optimal substructure and overlapping subproblem property, we can also utilise Dynamic programming to solve the problem. Instead of memoization, we can use the nested loop to implement the recursive relation.
The outer loop will run from i = 1 to N and the inner loop will run from j = 0 to i and use the recurrence relation to solve the problem.
Below is the implementation of the above approach:
C++
// Dynamic Programming C++ implementation// of LIS problem#include <bits/stdc++.h>using namespace std;// lis() returns the length of the longest// increasing subsequence in arr[] of size nint lis(int arr[], int n){ int lis[n]; lis[0] = 1; // Compute optimized LIS values in // bottom up manner for (int i = 1; i < n; i++) { lis[i] = 1; for (int j = 0; j < i; j++) if (arr[i] > arr[j] && lis[i] < lis[j] + 1) lis[i] = lis[j] + 1; } // Return maximum value in lis[] return *max_element(lis, lis + n);}// Driver program to test above functionint main(){ int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; int n = sizeof(arr) / sizeof(arr[0]); // Function call printf("Length of lis is %d\n", lis(arr, n)); return 0;} |
Length of lis is 5
Time Complexity: O(N2) As a nested loop is used.
Auxiliary Space: O(N) Use of any array to store LIS values at each index.
Please Refer Longest Increasing Subsequence for detailed article.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
