A subsequence of a given sequence of numbers can be thought of as the new sequen
ID: 1715885 • Letter: A
Question
A subsequence of a given sequence of numbers can be thought of as the new sequence obtained when you cross out some of the numbers. For example, 1,2,5,6,9, a subsequence of the sequence 3,1,2,17,5,6,9, is obtained by crossing out 3 and 17. Consider the following problem: Given a sequence of n number x1, . . . , xn, find the length of the longest increasing subsequence. i.e. a subsequence y1, . . . , yk with k as large as possible and such that y1 < y2 < . . . < yk. Give a dynamic programming algorithm for this problem.
Explanation / Answer
/* A Naive C/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 result */
int _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 function */
int main()
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr)/sizeof(arr[0]);
printf("Length of LIS is %d ", lis( arr, n ));
return 0;
}
/* Dynamic Programming C/C++ implementation of LIS problem */
#include<stdio.h>
#include<stdlib.h>
/* lis() returns the length of the longest increasing
subsequence in arr[] of size n */
int lis( int arr[], int n )
{
int *lis, i, j, max = 0;
lis = (int*) malloc ( sizeof( int ) * n );
/* Initialize LIS values for all indexes */
for ( i = 0; i < n; i++ )
lis[i] = 1;
/* Compute optimized LIS values in bottom up manner */
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;
/* Pick maximum of all LIS values */
for ( i = 0; i < n; i++ )
if ( max < lis[i] )
max = lis[i];
/* Free memory to avoid memory leak */
free( lis );
return max;
}
/* Driver program to test above function */
int main()
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr)/sizeof(arr[0]);
printf("Length of LIS is %d ", 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.