The task is to find the length of the longest subsequence in a given array of in
ID: 3821086 • Letter: T
Question
The task is to find the length of the longest subsequence in a given array of integers such that all elements of the subsequence are sorted in ascending order.
For example, the length of the LIS for {15, 27, 14, 38, 26, 55, 46, 65, 85 } is 6 and the longest increasing subsequence is {15, 27, 38, 55, 65, 85}.
Input : arr[] = {3, 10, 2, 1, 20}
Output : Length of LIS = 3
The longest increasing subsequence is 3, 10, 20
Input : arr[] = {3, 2}
Output : Length of LIS = 1
The longest increasing subsequences are {3} and {2}
Input : arr[] = {50, 3, 10, 7, 40, 80}
Output : Length of LIS = 4
The longest increasing subsequence is {3, 7, 40, 80}
Rule:Let, arr[0..n-1] be the input array and 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.
To find the LIS for a given array, we need to return max(L(i)) where 0 < i < n.
Follow the stated rules, complete the L = [....] array and find out what is the longest increasing subsequence for
arr = [100, 30, 90, 20, 29, 70, 109, 2, 22, 210, 55]
Show/Explain each step of filling L[i].
we use C++ coding
Explanation / Answer
#include<iostream>
using namespace std;
int lis( int arr[], int n )
{
int *lis, i, j, max = 0;
lis = (int*) malloc ( sizeof( int ) * n );
for (i = 0; i < n; i++ )
lis[i] = 1;
for (i = 1; i < n; i++ )
{
for (j = 0; j < i; j++ )
{
if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
{
lis[i] = lis[j] + 1;
}
}
}
for (i = 0; i < n; i++ )
{
if (max < lis[i])
max = lis[i];
}
free(lis);
return max;
}
int main()
{
int arr[] = { 100, 30, 90, 20, 29, 70, 109, 2, 22, 210, 55 };
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"Length of lis is"<<lis( arr, n );
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.